欢迎来到李耶的频道【LeetCode面试题】。四数之和18.四数之和题目给你一个由n个整数组成的数组nums和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]若两个四元组元素一一对应则认为两个四元组重复0 a, b, c, d na、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(leti0;inums.length-3;i){// 跳过重复的第一个数if(i0nums[i]nums[i-1])continue;for(letji1;jnums.length-2;j){// 跳过重复的第二个数if(ji1nums[j]nums[j-1])continue;letleftj1;letrightnums.length-1;while(leftright){constsumnums[i]nums[j]nums[left]nums[right];if(sumtarget){result.push([nums[i],nums[j],nums[left],nums[right]]);// 跳过重复的 leftwhile(leftrightnums[left]nums[left1])left;// 跳过重复的 rightwhile(leftrightnums[right]nums[right-1])right--;left;right--;}elseif(sumtarget){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);constnnums.length;for(leti0;in-3;i){if(i0nums[i]nums[i-1])continue;// 剪枝最小和大于 target后续更大直接 breakif(nums[i]nums[i1]nums[i2]nums[i3]target)break;// 剪枝最大和小于 target当前 i 不可能continueif(nums[i]nums[n-3]nums[n-2]nums[n-1]target)continue;for(letji1;jn-2;j){if(ji1nums[j]nums[j-1])continue;// 剪枝最小和大于 targetif(nums[i]nums[j]nums[j1]nums[j2]target)break;// 剪枝最大和小于 targetif(nums[i]nums[j]nums[n-2]nums[n-1]target)continue;letleftj1;letrightn-1;while(leftright){constsumnums[i]nums[j]nums[left]nums[right];if(sumtarget){result.push([nums[i],nums[j],nums[left],nums[right]]);while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;left;right--;}elseif(sumtarget){left;}else{right--;}}}}returnresult;}时间复杂度 / 空间复杂度O(n³) / O(log n)剪枝后实际运行效率大幅提升优势剪枝优化后性能更优面试中是加分项解法对比解法时间 / 空间复杂度剪枝优化推荐指数排序 双指针O(n³) / O(log n)❌⭐⭐⭐⭐排序 双指针 剪枝O(n³) / O(log n)✅⭐⭐⭐⭐⭐N 数之和通用模板可以继续扩展到 N 数之和functionnSum(nums,n,target,start){constresult[];if(n2){// 两数之和双指针letleftstart;letrightnums.length-1;while(leftright){constsumnums[left]nums[right];if(sumtarget){result.push([nums[left],nums[right]]);while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;left;right--;}elseif(sumtarget){left;}else{right--;}}}else{for(letistart;inums.length-n1;i){if(istartnums[i]nums[i-1])continue;constsubResultnSum(nums,n-1,target-nums[i],i1);for(letarrofsubResult){result.push([nums[i],...arr]);}}}returnresult;}扩展题N 数之和给定数组和正整数n找出所有和为target的n元组。最接近的四数之和给定数组和目标值target找出和最接近target的一个四元组返回这个和。四数之和 II给定四个整数数组A、B、C、D计算有多少个元组(i, j, k, l)使得A[i] B[j] C[k] D[l] 0。两数之和、三数之和、四数之和系列对比理解解题套路。“虚心使人进步骄傲使人落后。” —— 毛泽东关注李耶每天一道面试题一起卷起来