leetcode刷题：哈希表08 （四数之和）

第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]
]

比三数多一层循环。
这次依旧是以i为第一个数，i+1为第二个数j，然后j+1为第三个数left，length-1为第四个数right.
i为第一层遍历，此处要注意i的范围为[0,nums.length-4]。
依旧要先排序，j的基准是i+1，且j的范围是[i+1,nums.length-3]。
核心部分双指针不变。
i 和 j 在循环时要注意都要与前一个做比较，相同则跳过，但 j 不能和 i 的元素进行比较。因为这只是位置比较，i 和 j肯定不相遇。
最后要注意的是 left和left+1比。右移
right和right-1比，左移

    public static List<List<Integer>> fourSum(int[] nums, int target) {
    
        List<List<Integer>> result = new ArrayList<>();
        //至少四个数
        if (nums.length > 3) {
    
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 3; i++) {
    
                //升序，如果最小的都比目标值大，那还找啥
                if (nums[i] > target && nums[i] >= 0) {
    
                    break;
                }
                // i 为基准
                if (i > 0 && i < nums.length - 3 && nums[i] == nums[i - 1]) {
    
                    continue;
                }
                for (int j = i + 1; j < nums.length; j++) {
    
                    int left = j + 1;
                    int right = nums.length - 1;
                    System.out.println(i + " " + j);
                      // j 为第二个元素基准
                    if (j > i + 1 && nums[j] == nums[j - 1]) {
    
                        System.out.println("第二个元素和之前的重复，跳过本次循环");
                        System.out.println(i + " " + j + " " + left + " " + right);
                        continue;
                    }

                    while (left < right) {
    
                        int sum = nums[i] + nums[j] + nums[left] + nums[right];
                        System.out.println(i + " " + j + " " + left + " " + right);
                        System.out.println("和为" + sum);
                        if (sum == target) {
    
                            System.out.println("等于目标值");
                            result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                            System.out.println(result);
                            while (left < right && nums[left] == nums[left + 1]) {
    
                                left++;
                            }
                            while (left < right && nums[right] == nums[right - 1]) {
    
                                right--;
                            }
                            left++;
                            right--;
                            System.out.println(i + " " + j + " " + left + " " + right);
                        } else if (sum < target) {
    
                            left++;
                            System.out.println("小于目标值，左指针加加");
                        } else if ((sum > target)) {
    
                            right--;
                            System.out.println("大于目标值，右指针减减");
                        }
                    }

                    System.out.println(i + " " + j);
                }
                System.out.println(i);
            }
        }
        return result;
    }