18. 四数之和

一 题目

二 思路

• 类似于三数循环，三数循环是外面一个for固定一值，剩下的数里找加和
  现在是两个for固定两个值，剩下的数里找加和

三代码：

 public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new LinkedList<>();
        if (nums.length<4 ||nums==null){
            return res;
        }

        Arrays.sort(nums);
        int length =nums.length;
        for (int i = 0; i <length-3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1; j <length-2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                //说明此时剩下的两个数无论取什么值，四数之和一定大于 target，因此退出第二重循环；
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                //说明此时剩下的两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }

                //在后面的数里找到和为-nums[i]的数
                int l = j + 1;
                int r =length - 1;
                while (l < r) {
                    if (nums[l] + nums[r] == target - (nums[i] + nums[j])) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        // 特殊情况3 直接走到最后一个相同的数那里，避免多次循环
                        while (l + 1 <length && nums[l + 1] == nums[l]) {
                            l++;
                        }

                        while (r - 1 > 0 && nums[r - 1] == nums[r]) {
                            r--;
                        }

                        l++;
                        r--;
                    } else if (nums[l] + nums[r] > target-(nums[i] + nums[j])) {
                        r--;
                    } else if (nums[l] + nums[r] < target-(nums[i] + nums[j])) {
                        l++;
                    }
                }

            }
        }

        return res;
    }