18. 四数之和

给定一个包含 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]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums.length < 4) {
            return new ArrayList<>();
        }
        // 先对数组从小打到排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 固定前两个数
                int beforeTwo = nums[i] + nums[j];
                // 从前面固定的两个数之后开始开头和结尾指针
                int start = j + 1;
                int end = nums.length - 1;
                while (start < nums.length && end < nums.length && start < end) {
                    if (start > j + 1 && nums[start] == nums[start - 1]) {
                        start ++;
                        continue;
                    }
                    if (end < nums.length - 1 && nums[end] == nums[end + 1]) {
                        end --;
                        continue;
                    }
                    int endTwo = nums[start] + nums[end];
                    if (beforeTwo == target - endTwo) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end]));
                    }
                    if (endTwo < target - beforeTwo) {
                        start ++;
                    } else {
                        end --;
                    }
                }
            }
        }
        return result;
    }
}

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        num_len = len(nums)
        if num_len < 4:
            return result
        nums.sort()
        if sum(nums[0:4]) > target or sum(nums[-4:]) < target:
            return result
        for i in range(0, num_len - 3):
            if sum(nums[i:i+4]) > target:
                return result
            a = nums[i]
            # 剪枝
            if i > 0 and nums[i - 1] == a:
                continue
            for j in range(i + 1, num_len):
                # 剪枝
                if j - i - 1 > 0 and nums[j] == nums[j - 1]:
                    continue
                # 把a、b的值固定下来，a + b = target - (c + d)
                b = nums[j]
                k, l = j + 1, num_len - 1
                while k < l:
                    c, d = nums[k], nums[l]
                    if k - j - 1 > 0 and nums[k - 1] == c:
                        k += 1
                        continue
                    if l < num_len - 1 and nums[l + 1] == d:
                        l -= 1
                        continue
                    if a + b + c + d == target:
                        result.append([a, b, c, d])
                        k, l = k + 1, l - 1
                    elif a + b + c + d > target:
                        l -= 1
                    else:
                        k += 1
        return result

解题思路：
我们的目标是 a + b + c + d = target，
先将 nums数组从小到大排序，
固定 a + b 的值，c的值是b的下一个元素，d是nums数组的最后一个元素，
c, d分别从左右向中间移动，以找到 a + b = target - (c + d)
注意点：nums数组可能存在多个重复元素，要注意剪枝，对 a, b, c, d均需要，比如，
通过i获取a的时候，需要确保 nums[i] != nums[i - 1]