【LeetCode】18.四数之和

欢迎来到李耶的频道【LeetCode面试题】。

四数之和

18.四数之和

题目

给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c和d互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

解法一：排序 + 双指针（通用模板）

思路：在三数之和的基础上多加一层循环。先排序，然后用两层循环固定前两个数，再用双指针在右侧区间寻找后两个数。注意每一层都需要跳过重复元素。

functionfourSum(nums,target){constresult=[];nums.sort((a,b)=>a-b);for(leti=0;i<nums.length-3;i++){// 跳过重复的第一个数if(i>0&&nums[i]===nums[i-1])continue;for(letj=i+1;j<nums.length-2;j++){// 跳过重复的第二个数if(j>i+1&&nums[j]===nums[j-1])continue;letleft=j+1;letright=nums.length-1;while(left<right){constsum=nums[i]+nums[j]+nums[left]+nums[right];if(sum===target){result.push([nums[i],nums[j],nums[left],nums[right]]);// 跳过重复的 leftwhile(left<right&&nums[left]===nums[left+1])left++;// 跳过重复的 rightwhile(left<right&&nums[right]===nums[right-1])right--;left++;right--;}elseif(sum<target){left++;}else{right--;}}}}returnresult;}

• 时间复杂度 / 空间复杂度：O(n³) / O(log n) 或 O(n)
  • 三层循环 O(n³)，排序 O(n log n)，总体 O(n³)
  • 空间复杂度取决于排序算法
• 优势：最推荐，是三数之和的通用扩展，模板可以继续扩展到 N 数之和

解法二：排序 + 双指针 + 剪枝优化

思路：在解法一的基础上增加剪枝逻辑，提前跳过不可能的情况，大幅提升效率。

functionfourSum(nums,target){constresult=[];nums.sort((a,b)=>a-b);constn=nums.length;for(leti=0;i<n-3;i++){if(i>0&&nums[i]===nums[i-1])continue;// 剪枝：最小和大于 target，后续更大，直接 breakif(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)break;// 剪枝：最大和小于 target，当前 i 不可能，continueif(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target)continue;for(letj=i+1;j<n-2;j++){if(j>i+1&&nums[j]===nums[j-1])continue;// 剪枝：最小和大于 targetif(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target)break;// 剪枝：最大和小于 targetif(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target)continue;letleft=j+1;letright=n-1;while(left<right){constsum=nums[i]+nums[j]+nums[left]+nums[right];if(sum===target){result.push([nums[i],nums[j],nums[left],nums[right]]);while(left<right&&nums[left]===nums[left+1])left++;while(left<right&&nums[right]===nums[right-1])right--;left++;right--;}elseif(sum<target){left++;}else{right--;}}}}returnresult;}

• 时间复杂度 / 空间复杂度：O(n³) / O(log n)，剪枝后实际运行效率大幅提升
• 优势：剪枝优化后性能更优，面试中是加分项

解法对比

N 数之和通用模板

可以继续扩展到 N 数之和：

functionnSum(nums,n,target,start){constresult=[];if(n===2){// 两数之和（双指针）letleft=start;letright=nums.length-1;while(left<right){constsum=nums[left]+nums[right];if(sum===target){result.push([nums[left],nums[right]]);while(left<right&&nums[left]===nums[left+1])left++;while(left<right&&nums[right]===nums[right-1])right--;left++;right--;}elseif(sum<target){left++;}else{right--;}}}else{for(leti=start;i<nums.length-n+1;i++){if(i>start&&nums[i]===nums[i-1])continue;constsubResult=nSum(nums,n-1,target-nums[i],i+1);for(letarrofsubResult){result.push([nums[i],...arr]);}}}returnresult;}

扩展题

1. N 数之和：给定数组和正整数n，找出所有和为target的n元组。
2. 最接近的四数之和：给定数组和目标值target，找出和最接近target的一个四元组，返回这个和。
3. 四数之和 II：给定四个整数数组A、B、C、D，计算有多少个元组(i, j, k, l)使得A[i] + B[j] + C[k] + D[l] == 0。
4. 两数之和、三数之和、四数之和系列对比，理解解题套路。

“虚心使人进步，骄傲使人落后。” —— 毛泽东

关注李耶，每天一道面试题，一起卷起来 🔥