四数之和

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum

题目描述:

给你一个由 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
-109 <= nums[i] <= 109
-109 <= target <= 109

思路:

相比三数之和,多了一层循环,思路还是排序+双指针。

• 先对数组nums进行排序.
• 遍历nums,最外层循环(0 <= i < nums.length)
• 第二层循环(i + 1 <= j < nums.length)
• 第三层循环初始化l = j + 1,r = nums.length - 1;
• 比较 nums[i] + nums[j] + nums[l] + nums[r]之和与target的大小
• • 相等，保存结果
• • 大于，r-- (因为数组有序,r--则和减小)
• • 小于，l++(因为数组有序,l++则和增加)
• 去重:判断当前元素与上(下)一个元素是否相同，如果是则跳过,因为该元素的结果已经获取过一次

代码实现:

class Solution {
    public List<List<Integer>> result = new ArrayList();

    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        if (len < 4) return result;
        Arrays.sort(nums);
  
        for (int i = 0; i < len; i++) {
             // 去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < len; j++) {
                if (j > (i + 1) && nums[j] == nums[j - 1]) continue;
                int l = j + 1;
                int r = len - 1;
                while (l < r) {
                     // 去重
                    if (nums[i] + nums[j] + nums[l] + nums[r] == target) {
                        List<Integer> list = new ArrayList();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[l]);
                        list.add(nums[r]);
                        result.add(list);
                        // 去重
                        while (l < r && nums[l] == nums[l + 1]) {
                            l++;
                        }
                         // 去重
                        while (l < r & nums[r] == nums[r - 1]) {
                            r--;
                        }
                        l++;
                        r--;
                    } else if (nums[i] + nums[j] + nums[l] + nums[r] < target) {
                        l++;
                    } else {
                        r--;
                    }
                }
            }
        }
        return result;
    }
}