2025年前端算法面试题及答案

2025年前端算法面试题及答案给定一个包含n个整数的数组nums和一个目标值target，找出数组中所有不重复的三元组[nums[i],nums[j],nums[k]]，使得i≠j≠k且nums[i]+nums[j]+nums[k]=target。要求结果中不能包含重复的三元组。思路：首先对数组进行排序，便于后续去重和双指针操作。固定第一个元素nums[i]，然后在i之后的子数组中使用双指针法寻找两个数，使其和为target-nums[i]。遍历时需跳过重复的元素，避免结果中出现重复三元组。代码实现：```javascriptfunctionthreeSum(nums,target){nums.sort((a,b)=>ab);constres=[];constn=nums.length;for(leti=0;i<n;i++){if(i>0&&nums[i]===nums[i1])continue;//跳过重复的第一个元素letleft=i+1,right=n1;constremain=targetnums[i];while(left<right){constsum=nums[left]+nums[right];if(sum===remain){res.push([nums[i],nums[left],nums[right]]);//跳过左指针重复元素while(left<right&&nums[left]===nums[left+1])left++;//跳过右指针重复元素while(left<right&&nums[right]===nums[right1])right--;left++;right--;}elseif(sum<remain){left++;//和偏小，左指针右移}else{right--;//和偏大，右指针左移}}}returnres;}```复杂度分析：排序的时间复杂度为O(nlogn)，外层循环遍历每个元素为O(n)，双指针遍历为O(n)，总时间复杂度O(n²)；空间复杂度主要由排序的栈空间决定，为O(logn)。给定一个字符串s，找到s中最长的回文子串。思路：回文子串的中心可以是单个字符（奇数长度）或两个相同字符（偶数长度）。遍历每个可能的中心，向左右扩展，记录最长回文子串的起始位置和长度。代码实现：```javascriptfunctionlongestPalindrome(s){if(s.length<2)returns;letstart=0,maxLen=1;constexpandAroundCenter=(left,right)=>{while(left>=0&&right<s.length&&s[left]===s[right]){constcurrentLen=rightleft+1;if(currentLen>maxLen){maxLen=currentLen;start=left;}left--;right++;}};for(leti=0;i<s.length;i++){expandAroundCenter(i,i);//奇数长度回文expandAroundCenter(i,i+1);//偶数长度回文}returns.substring(start,start+maxLen);}```复杂度分析：每个中心最多扩展O(n)次，共有O(n)个中心，时间复杂度O(n²)；仅使用常数额外空间，空间复杂度O(1)。给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，返回null。思路：使用快慢指针法。快指针每次移动两步，慢指针每次移动一步，若链表有环则两者会相遇。相遇后，将快指针重新指向头节点，快慢指针每次移动一步，再次相遇的节点即为环的入口。代码实现：```javascriptfunctiondetectCycle(head){if(!head||!head.next)returnnull;letslow=head,fast=head;while(fast&&fast.next){slow=slow.next;fast=fast.next.next;if(slow===fast){//存在环fast=head;//快指针重置到头节点while(slow!==fast){slow=slow.next;fast=fast.next;}returnslow;}}returnnull;//无环}```复杂度分析：遍历链表的时间复杂度为O(n)，仅使用常数额外空间，空间复杂度O(1)。给定二叉树的根节点root和两个节点p、q，找出它们的最近公共祖先（LCA）。思路：递归遍历二叉树。若当前节点是p或q，直接返回当前节点；否则递归查找左右子树。若左右子树均能找到p或q，则当前节点为LCA；若仅左子树找到，返回左子树结果；若仅右子树找到，返回右子树结果。代码实现：```javascriptfunctionlowestCommonAncestor(root,p,q){if(!root||root===p||root===q)returnroot;constleft=lowestCommonAncestor(root.left,p,q);constright=lowestCommonAncestor(root.right,p,q);if(left&&right)returnroot;//左右子树均有结果，当前节点为LCAreturnleft||right;//仅一侧有结果，返回该结果}```复杂度分析：每个节点仅遍历一次，时间复杂度O(n)；递归栈的深度最坏为O(n)（链表状树），空间复杂度O(n)。给定一个整数数组nums，找到其中最长递增子序列（LIS）的长度。思路：维护一个数组tails，其中tails[i]表示长度为i+1的递增子序列的最小末尾元素。遍历nums，对每个元素使用二分查找确定其在tails中的位置，更新tails以保持其性质。代码实现：```javascriptfunctionlengthOfLIS(nums){consttails=[];for(constnumofnums){letleft=0,right=tails.length;while(left<right){//二分查找第一个大于等于num的位置constmid=(left+right)>>1;if(tails[mid]<num){left=mid+1;}else{right=mid;}}tails[left]=num;//替换或追加}returntails.length;}```复杂度分析：遍历数组为O(n)，每次二分查找为O(logn)，总时间复杂度O(nlogn)；tails数组的空间复杂度为O(n)。用非递归方式实现快速排序，对数组进行升序排序。思路：使用栈模拟递归过程。每次选择基准元素，将数组划分为左右两部分，将子区间的左右索引压入栈中，循环处理直到栈为空。代码实现：```javascriptfunctionquickSort(arr){if(arr.length<=1)returnarr;conststack=[];stack.push(0,arr.length1);//初始区间[0,n-1]while(stack.length>0){constright=stack.pop();constleft=stack.pop();constpivotIndex=partition(arr,left,right);//处理左子区间if(left<pivotIndex1){stack.push(left,pivotIndex1);}//处理右子区间if(pivotIndex+1<right){stack.push(pivotIndex+1,right);}}returnarr;}functionpartition(arr,left,right){constpivot=arr[right];//选择右边界为基准leti=left1;//记录小于基准的元素的右边界for(letj=left;j<right;j++){if(arr[j]<=pivot){i++;[arr[i],arr[j]]=[arr[j],arr[i]];//交换元素}}[arr[i+1],arr[right]]=[arr[right],arr[i+1]];//将基准放到正确位置returni+1;//返回基准的索引}```复杂度分析：平均时间复杂度O(nlogn)，最坏情况（已排序数组）为O(n²)；栈的最大深度为O(logn)，空间复杂度O(logn)。给定一个非负整数数组nums，每个元素表示在该位置可以跳跃的最大长度。从第一个位置出发，求到达最后一个位置的最少跳跃次数。思路：贪心算法。维护当前能到达的最远位置currentEnd、下一步能到达的最远位置farthest和跳跃次数jumps。遍历数组，当到达currentEnd时，必须进行一次跳跃，并更新currentEnd为farthest。代码实现：```javascriptfunctionjump(nums){letjumps=0,currentEnd=0,farthest=0;for(leti=0;i<nums.length1;i++){farthest=Math.max(farthest,i+nums[i]);//更新下一步最远位置if(i===currentEnd){//到达当前最远位置，必须跳跃jumps++;currentEnd=farthest;//更新当前最远位置if(currentEnd>=nums.length1)break;//提前终止}}returnjumps;}```复杂度分析：仅遍历数组一次，时间复杂度O(n)；使用常数额外空间，空间复杂度O(1)。假设数组nums是一个旋转过的有序数组（可能有重复元素），找出其中的最小元素。思路：二分查找。比较中间元素nums[mid]与右边界元素nums[right]：若nums[mid]>nums[right]，说明最小值在右半部分；若nums[mid]<nums[right]，说明最小值在左半部分；若相等，右边界左移一位以缩小范围。代码实现：```javascriptfunctionfindMin(nums){letleft=0,right=nums.length1;while(left<right){constmid=(left+right)>>1;if(nums[mid]>nums[right]){left=mid+1;//最小值在右半部分}elseif(nums[mid]<nums[right]){right=mid;//最小值在左半部分}else{right--;//处理重复元素，右边界左移}}returnnums[left];}```复杂度分析：最坏情况下（所有元素相同）时间复杂度O(n)，平均为O(logn)；空间复杂度O(1)。给定一个由'1'（陆地）和'0'（水）组成的二维网格grid，计算岛屿的数量。岛屿被水包围，由相邻的陆地水平或垂直连接而成。思路：BFS遍历。遍历每个网格，遇到'1'时进行BFS，将所有相连的'1'标记为'0'（表示已访问），并增加岛屿计数。代码实现：```javascriptfunctionnumIslands(grid){if(grid.length===0)return0;constrows=grid.length,cols=grid[0].length;letcount=0;constdirections=[[-1,0],[1,0],[0,-1],[0,1]];//上下左右四个方向for(leti=0;i<rows;i++){for(letj=0;j<cols;j++){if(grid[i][j]==='1'){//发现新岛屿count++;constqueue=[[i,j]];grid[i][j]='0';//标记为已访问while(queue.length>0){const[x,y]=queue.shift();for(const[dx,dy]ofdirections){//遍历四个方向constnx=x+dx,ny=y+dy;if(nx>=0&&nx<rows&&ny>=0&&ny<cols&&grid[nx][ny]==='1'){grid[nx][ny]='0';//标记为已访问queue.push([nx,ny]);}}}}}}returncount;}```复杂度分析：每个网格最多被访问一次，时间复杂度O(mn)（m为行数，n为列数）；BFS队列的最大空间为O(mn)（全为陆地），空间复杂度O(mn)。用两个栈实现一个队列，支持push、pop、peek、empty操作。思路：使用栈1（stack1）存储入队元素，栈2（stack2）存储出队元素。当需要出队或查看队首时，若栈2为空，将栈1的所有元素弹出并压入栈2，此时栈2的顶部即为队首元素。