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

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你可以按任意顺序返回答案 。示例 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问题publicListListIntegerfourSum(int[]nums,inttarget){// 最终要返回的结果列表ListListIntegerresultnewArrayList();// 对数组进行排序Arrays.sort(nums);// 给定左右两个外围指针intleftOut0;intrightOutnums.length-1;// 两对双指针遍历数组while(leftOutrightOut-2){// 边界条件判断if(nums[leftOut]target)break;// 对leftOut和rightOut进行剪枝if(leftOut0nums[leftOut]nums[leftOut-1]){leftOut;continue;}if(rightOutnums.length-1nums[rightOut]nums[rightOut1]){rightOut--;continue;}// 初始化左右两个内部指针intleftInleftOut1;intrightInrightOut-1;while(leftInrightIn){intsumnums[leftIn]nums[leftOut]nums[rightOut]nums[rightIn];if(sumtarget){rightIn--;continue;}elseif(sumtarget){leftIn;continue;}else{// 加入结果四元组result.add(Arrays.asList(nums[leftIn],nums[leftOut],nums[rightIn],nums[rightOut]));// 对leftIn和rightIn去重剪枝while(leftInrightInnums[leftIn]nums[leftIn1])leftIn;while(leftInrightInnums[rightIn]nums[rightIn-1])rightIn--;// 过滤掉一组正确解rightIn--;leftIn;}}if(nums[rightOut]nums[leftOut]target){rightOut--;}else{leftOut;}}returnresult;}}正确解法classSolution{publicListListIntegerfourSum(int[]nums,inttarget){// 最终要返回的列表ListListIntegerresultnewArrayList();// 对数组进行排序Arrays.sort(nums);// 固定前两个数用剩余部分进行双指针扫描for(inti0;inums.length-3;i){// 边界条件判断防止大数溢出longmin(long)nums[i]nums[i1]nums[i2]nums[i3];if(mintarget)break;longmax(long)nums[i]nums[nums.length-1]nums[nums.length-2]nums[nums.length-3];if(maxtarget)continue;// 对i去重if(i0nums[i]nums[i-1])continue;// 固定第二个数for(intji1;jnums.length-2;j){// 对j去重if(ji1nums[j]nums[j-1])continue;// 给定双指针intleftj1;intrightnums.length-1;while(leftright){// 防止大数溢出longsum(long)nums[i]nums[j]nums[left]nums[right];if(sumtarget){right--;continue;}elseif(sumtarget){left;continue;}else{result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));// 对left和right去重while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;// 过滤一组正确解left;right--;}}}}returnresult;}}