18.四数之和

题目链接：https://leetcode-cn.com/problems/4sum/

难度：中等

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解法一：双指针法 + 排序

解法思路：

若是做过15. 三数之和会发现这两个题是一个解题思路。

我们利用一个双重循环a和b来控制四个数中最小的两数，再用双指针l和r来控制另外两数。

计算：sum = nums[a]+nums[b]+nums[l]+nums[r];

若sum == target，则把这四个数添加到结果数组中

若sum > target，则说明r太大了，将r--，将指针r向左移动。

若sum < target，则说明l太大了，将l++，将指针l向右移动。

解决重复结果问题：

我们在四层变量值改变的时候，可以判断一下，是否和上一次的值相等，若相等，直接跳过这次循环。

时间复杂度优化：

我们在外两层a和b变量值改变的时候，可以计算一下，他们的最大值和最小值，若最大值比target还小，或者最小值比target还大，都可以直接跳过。

image.png

代码:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        int l,r;
        int sum;
        int max,min;
        Arrays.sort(nums);
        int len = nums.length;
        
        for(int a = 0;a<len-3;a++) {
            //当nums[a] == nums[a-1] 直接跳过
            if(a>0 && nums[a] == nums[a-1]) {
                continue;
            }
            
            //获取当前的最大值，如果最大值比目标值还小，直接跳过
            max = nums[a]+nums[len-3]+nums[len-2]+nums[len-1];
            if(max<target) {
                continue;
            }
            
            //获取当前的最小值，如果最小值比目标值还大，直接跳过
            min = nums[a]+nums[a+1]+nums[a+2]+nums[a+3];
            if(min>target) {
                continue;
            }
            
            for(int b = a+1;b<len-2;b++) {
                //当nums[b] == nums[b-1]直接跳过
                if(b>a+1 && nums[b] == nums[b-1]) {
                    continue;
                }
                l = b+1;
                r = len-1;
                
                //获取当前的最大值，如果最大值比目标值还小，直接跳过
                max = nums[a]+nums[b]+nums[r-1]+nums[r];
                if(max<target) {
                    continue;
                }
                
                //获取当前的最小值，如果最小值比目标值还大，直接跳过
                min = nums[a]+nums[b]+nums[l]+nums[l+1];
                if(min>target) {
                    continue;
                }
                
                while(l<r) {
                    sum = nums[a]+nums[b]+nums[l]+nums[r];
                    if(sum == target) {
                        results.add(Arrays.asList(nums[a],nums[b],nums[l],nums[r]));
                        l++;
                        r--;
                        
                        //当nums[r]==nums[r+1]直接跳过
                        while(r<len-1 && r>l && nums[r]==nums[r+1]) {
                            r--;
                        }
                        //当nums[l]==nums[l-1]直接跳过
                        while(l>b+1 && r>l && nums[l]==nums[l-1]) {
                            l++;
                        }
                    }else if(sum > target) {
                        r--;
                    }else {
                        l++;
                    }
                }
            }
        }
        return results;
    }
}