2025年前端算法面試題及答案給定一個包含n個整數(shù)的數(shù)組nums和一個目標(biāo)值target，找出數(shù)組中所有不重復(fù)的三元組[nums[i],nums[j],nums[k]]，使得i≠j≠k且nums[i]+nums[j]+nums[k]=target。要求結(jié)果中不能包含重復(fù)的三元組。思路：首先對數(shù)組進(jìn)行排序，便于后續(xù)去重和雙指針操作。固定第一個元素nums[i]，然后在i之后的子數(shù)組中使用雙指針法尋找兩個數(shù)，使其和為target-nums[i]。遍歷時需跳過重復(fù)的元素，避免結(jié)果中出現(xiàn)重復(fù)三元組。代碼實(shí)現(xiàn)：```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;//跳過重復(fù)的第一個元素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]]);//跳過左指針重復(fù)元素while(left<right&&nums[left]===nums[left+1])left++;//跳過右指針重復(fù)元素while(left<right&&nums[right]===nums[right1])right--;left++;right--;}elseif(sum<remain){left++;//和偏小，左指針右移}else{right--;//和偏大，右指針左移}}}returnres;}```復(fù)雜度分析：排序的時間復(fù)雜度為O(nlogn)，外層循環(huán)遍歷每個元素為O(n)，雙指針遍歷為O(n)，總時間復(fù)雜度O(n2)；空間復(fù)雜度主要由排序的?？臻g決定，為O(logn)。給定一個字符串s，找到s中最長的回文子串。思路：回文子串的中心可以是單個字符（奇數(shù)長度）或兩個相同字符（偶數(shù)長度）。遍歷每個可能的中心，向左右擴(kuò)展，記錄最長回文子串的起始位置和長度。代碼實(shí)現(xiàn)：```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);//奇數(shù)長度回文expandAroundCenter(i,i+1);//偶數(shù)長度回文}returns.substring(start,start+maxLen);}```復(fù)雜度分析：每個中心最多擴(kuò)展O(n)次，共有O(n)個中心，時間復(fù)雜度O(n2)；僅使用常數(shù)額外空間，空間復(fù)雜度O(1)。給定一個鏈表的頭節(jié)點(diǎn)head，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。如果鏈表無環(huán)，返回null。思路：使用快慢指針法?？熘羔樏看我苿觾刹?，慢指針每次移動一步，若鏈表有環(huán)則兩者會相遇。相遇后，將快指針重新指向頭節(jié)點(diǎn)，快慢指針每次移動一步，再次相遇的節(jié)點(diǎn)即為環(huán)的入口。代碼實(shí)現(xiàn)：```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){//存在環(huán)fast=head;//快指針重置到頭節(jié)點(diǎn)while(slow!==fast){slow=slow.next;fast=fast.next;}returnslow;}}returnnull;//無環(huán)}```復(fù)雜度分析：遍歷鏈表的時間復(fù)雜度為O(n)，僅使用常數(shù)額外空間，空間復(fù)雜度O(1)。給定二叉樹的根節(jié)點(diǎn)root和兩個節(jié)點(diǎn)p、q，找出它們的最近公共祖先（LCA）。思路：遞歸遍歷二叉樹。若當(dāng)前節(jié)點(diǎn)是p或q，直接返回當(dāng)前節(jié)點(diǎn)；否則遞歸查找左右子樹。若左右子樹均能找到p或q，則當(dāng)前節(jié)點(diǎn)為LCA；若僅左子樹找到，返回左子樹結(jié)果；若僅右子樹找到，返回右子樹結(jié)果。代碼實(shí)現(xiàn)：```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;//左右子樹均有結(jié)果，當(dāng)前節(jié)點(diǎn)為LCAreturnleft||right;//僅一側(cè)有結(jié)果，返回該結(jié)果}```復(fù)雜度分析：每個節(jié)點(diǎn)僅遍歷一次，時間復(fù)雜度O(n)；遞歸棧的深度最壞為O(n)（鏈表狀樹），空間復(fù)雜度O(n)。給定一個整數(shù)數(shù)組nums，找到其中最長遞增子序列（LIS）的長度。思路：維護(hù)一個數(shù)組tails，其中tails[i]表示長度為i+1的遞增子序列的最小末尾元素。遍歷nums，對每個元素使用二分查找確定其在tails中的位置，更新tails以保持其性質(zhì)。代碼實(shí)現(xiàn)：```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;}```復(fù)雜度分析：遍歷數(shù)組為O(n)，每次二分查找為O(logn)，總時間復(fù)雜度O(nlogn)；tails數(shù)組的空間復(fù)雜度為O(n)。用非遞歸方式實(shí)現(xiàn)快速排序，對數(shù)組進(jìn)行升序排序。思路：使用棧模擬遞歸過程。每次選擇基準(zhǔn)元素，將數(shù)組劃分為左右兩部分，將子區(qū)間的左右索引壓入棧中，循環(huán)處理直到棧為空。代碼實(shí)現(xiàn)：```javascriptfunctionquickSort(arr){if(arr.length<=1)returnarr;conststack=[];stack.push(0,arr.length1);//初始區(qū)間[0,n-1]while(stack.length>0){constright=stack.pop();constleft=stack.pop();constpivotIndex=partition(arr,left,right);//處理左子區(qū)間if(left<pivotIndex1){stack.push(left,pivotIndex1);}//處理右子區(qū)間if(pivotIndex+1<right){stack.push(pivotIndex+1,right);}}returnarr;}functionpartition(arr,left,right){constpivot=arr[right];//選擇右邊界為基準(zhǔn)leti=left1;//記錄小于基準(zhǔn)的元素的右邊界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]];//將基準(zhǔn)放到正確位置returni+1;//返回基準(zhǔn)的索引}```復(fù)雜度分析：平均時間復(fù)雜度O(nlogn)，最壞情況（已排序數(shù)組）為O(n2)；棧的最大深度為O(logn)，空間復(fù)雜度O(logn)。給定一個非負(fù)整數(shù)數(shù)組nums，每個元素表示在該位置可以跳躍的最大長度。從第一個位置出發(fā)，求到達(dá)最后一個位置的最少跳躍次數(shù)。思路：貪心算法。維護(hù)當(dāng)前能到達(dá)的最遠(yuǎn)位置currentEnd、下一步能到達(dá)的最遠(yuǎn)位置farthest和跳躍次數(shù)jumps。遍歷數(shù)組，當(dāng)?shù)竭_(dá)currentEnd時，必須進(jìn)行一次跳躍，并更新currentEnd為farthest。代碼實(shí)現(xiàn)：```javascriptfunctionjump(nums){letjumps=0,currentEnd=0,farthest=0;for(leti=0;i<nums.length1;i++){farthest=Math.max(farthest,i+nums[i]);//更新下一步最遠(yuǎn)位置if(i===currentEnd){//到達(dá)當(dāng)前最遠(yuǎn)位置，必須跳躍jumps++;currentEnd=farthest;//更新當(dāng)前最遠(yuǎn)位置if(currentEnd>=nums.length1)break;//提前終止}}returnjumps;}```復(fù)雜度分析：僅遍歷數(shù)組一次，時間復(fù)雜度O(n)；使用常數(shù)額外空間，空間復(fù)雜度O(1)。假設(shè)數(shù)組nums是一個旋轉(zhuǎn)過的有序數(shù)組（可能有重復(fù)元素），找出其中的最小元素。思路：二分查找。比較中間元素nums[mid]與右邊界元素nums[right]：若nums[mid]>nums[right]，說明最小值在右半部分；若nums[mid]<nums[right]，說明最小值在左半部分；若相等，右邊界左移一位以縮小范圍。代碼實(shí)現(xiàn)：```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--;//處理重復(fù)元素，右邊界左移}}returnnums[left];}```復(fù)雜度分析：最壞情況下（所有元素相同）時間復(fù)雜度O(n)，平均為O(logn)；空間復(fù)雜度O(1)。給定一個由'1'（陸地）和'0'（水）組成的二維網(wǎng)格grid，計算島嶼的數(shù)量。島嶼被水包圍，由相鄰的陸地水平或垂直連接而成。思路：BFS遍歷。遍歷每個網(wǎng)格，遇到'1'時進(jìn)行BFS，將所有相連的'1'標(biāo)記為'0'（表示已訪問），并增加島嶼計數(shù)。代碼實(shí)現(xiàn)：```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'){//發(fā)現(xiàn)新島嶼count++;constqueue=[[i,j]];grid[i][j]='0';//標(biāo)記為已訪問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';//標(biāo)記為已訪問queue.push([nx,ny]);}}}}}}returncount;}```復(fù)雜度分析：每個網(wǎng)格最多被訪問一次，時間復(fù)雜度O(mn)（m為行數(shù)，n為列數(shù)）；BFS隊列的最大空間為O(mn)（全為陸地），空間復(fù)雜度O(mn)。用兩個棧實(shí)現(xiàn)一個隊列，支持push、pop、peek、empty操作。思路：使用棧1（stack1）存儲入隊元素，棧2（stack2）存儲出隊元素。當(dāng)需要出隊或查看隊首時，若棧2為空，將棧1的所有元素彈出并壓入棧2，此時棧2的頂部即為隊首元素。