【LeetCode-中等题】18. 四数之和

题目

方法一：双指针（定2动2）

这题可以参考【LeetCode-中等题】15. 三数之和
区别在于，三数之和只需要用一个for循环定住一个数，然后设置两个前后指针来根据sum的值和目标值比较来滑动指针

那么这题也是同理的，我们需要做的事就是定住2个数，要用两个for循环定住两个数，然后设置两个前后指针来根据sum的值和目标值比较来滑动指针

里面的处理细节很多需要注意，提前处理一些不可能满足条件的情况，减少时间复杂度

class Solution {
//for定2 指针动2public List<List<Integer>> fourSum(int[] nums, int target) {int len =  nums.length;if(nums == null||len < 4 ) return new ArrayList<>();List<List<Integer>> res = new ArrayList<>();List<Integer> zres = null;Arrays.sort(nums);for(int i = 0 ;i< len-3 ;i++){//本身就是排序的数组  若第一个数就大于等于target了那么再加上任何一个数都会大于target，所以直接break//    if(nums[i]>target)  break;//这个条件不能要（对比LeetCode 15. 三数之和）  如果target是负数，第一个数大于target  在往下加可能会越来越小也是可以=taget的//但是如果target为0或正数，那么第一个数大于target  往下加会越来越大//去重操作  如果nums[i]==nums[i-1] 会得到一份与nums[i-1]一样的结果集if(i>0&&nums[i]==nums[i-1]) continue;// 若以i开头的四个元素就已经大于target了 那就无需做任何操作了，没必要了，在往后面加再怎么也会大于targetif((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;// 若以i开头元素和数组末尾的三个元素就还小于target了 那就没必要做此次循环，毕竟i加上后面最大的三个数都比target小if((long)nums[i]+nums[len-1]+nums[len-2]+nums[len-3] < target) continue;for(int j = i+1 ;j< len-2 ;j++){//这里就和 LeetCode 15. 三数之和  一样的原理  唯一多了一个提前判断// 这里的三个if与上面同理  if(j>i+1&&nums[j]==nums[j-1]) continue;if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2] > target) break;if((long)nums[i]+nums[j]+nums[len-1]+nums[len-2] < target) continue;int left = j+1;int right = len-1;while(left < right){long sum =(long) nums[i]+nums[j]+nums[left]+nums[right];if(sum == target) {zres = new ArrayList<>();//满足要求的子结果集zres.add(nums[i]);zres.add(nums[j]);zres.add(nums[left]);zres.add(nums[right]);res.add(zres);//加入大结果集while(left < right &&nums[left]==nums[left+1]) left++;//两个指针的去重while(left < right &&nums[right]==nums[right-1]) right--;left++;//移动指针到不重复的新区域right--;}else if(sum >target)  right--;//缩小数值else left++;//扩大数值}}}return res;}
}