LeetCode--18.四数之和（双指针法）

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

题解

尝试复刻三数之和，使用O ( n 2 ) O(n^2)O(n2)时间复杂度解决，失败：

固定两个指针，再用另外两个指针进行扫描O ( n 3 ) O(n^3)O(n3)时间复杂度解决

代码

错误解法：

classSolution{// 这种双指针写法过于贪心，无法适用于4Sum问题publicList<List<Integer>>fourSum(int[]nums,inttarget){// 最终要返回的结果列表List<List<Integer>>result=newArrayList<>();// 对数组进行排序Arrays.sort(nums);// 给定左右两个外围指针intleftOut=0;intrightOut=nums.length-1;// 两对双指针遍历数组while(leftOut<rightOut-2){// 边界条件判断if(nums[leftOut]>target)break;// 对leftOut和rightOut进行剪枝if(leftOut>0&&nums[leftOut]==nums[leftOut-1]){leftOut++;continue;}if(rightOut<nums.length-1&&nums[rightOut]==nums[rightOut+1]){rightOut--;continue;}// 初始化左右两个内部指针intleftIn=leftOut+1;intrightIn=rightOut-1;while(leftIn<rightIn){intsum=nums[leftIn]+nums[leftOut]+nums[rightOut]+nums[rightIn];if(sum>target){rightIn--;continue;}elseif(sum<target){leftIn++;continue;}else{// 加入结果四元组result.add(Arrays.asList(nums[leftIn],nums[leftOut],nums[rightIn],nums[rightOut]));// 对leftIn和rightIn去重剪枝while(leftIn<rightIn&&nums[leftIn]==nums[leftIn+1])leftIn++;while(leftIn<rightIn&&nums[rightIn]==nums[rightIn-1])rightIn--;// 过滤掉一组正确解rightIn--;leftIn++;}}if(nums[rightOut]+nums[leftOut]>=target){rightOut--;}else{leftOut++;}}returnresult;}}

正确解法：

classSolution{publicList<List<Integer>>fourSum(int[]nums,inttarget){// 最终要返回的列表List<List<Integer>>result=newArrayList<>();// 对数组进行排序Arrays.sort(nums);// 固定前两个数，用剩余部分进行双指针扫描for(inti=0;i<nums.length-3;i++){// 边界条件判断，防止大数溢出longmin=(long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3];if(min>target)break;longmax=(long)nums[i]+nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3];if(max<target)continue;// 对i去重if(i>0&&nums[i]==nums[i-1])continue;// 固定第二个数for(intj=i+1;j<nums.length-2;j++){// 对j去重if(j>i+1&&nums[j]==nums[j-1])continue;// 给定双指针intleft=j+1;intright=nums.length-1;while(left<right){// 防止大数溢出longsum=(long)nums[i]+nums[j]+nums[left]+nums[right];if(sum>target){right--;continue;}elseif(sum<target){left++;continue;}else{result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));// 对left和right去重while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;// 过滤一组正确解left++;right--;}}}}returnresult;}}