Leetcode: hash table 08 (sum of four numbers)

The first 18 topic . Sum of four numbers

Force button topic link

The question ： Given an inclusion n Array of integers nums And a target value target, Judge nums Are there four elements in a,b,c and d , bring a + b + c + d The value of is equal to target equal ？ Find all quadruples that meet the conditions and are not repeated .

Be careful ：

The answer cannot contain duplicate quadruples .

Example ：
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
The set of quads satisfying the requirements is ：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

It's more than three .
This time it's still i For the first number ,i+1 For the second number j, then j+1 For the third number left,length-1 For the fourth number right.
i Traverse for the first layer , Notice here i For the range of [0,nums.length-4].
Still sort first ,j The benchmark is i+1, And j The range is [i+1,nums.length-3].
The core double pointer remains unchanged .
i and j Pay attention to the comparison with the previous one in the cycle , If the same, skip , but j Unable to join i Compare the elements of . Because this is just a position comparison ,i and j Certainly not .
Last but not least left and left+1 Than . Move right
right and right-1 Than , Move left

    public static List<List<Integer>> fourSum(int[] nums, int target) {
    
        List<List<Integer>> result = new ArrayList<>();
        // At least four numbers 
        if (nums.length > 3) {
    
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 3; i++) {
    
                // Ascending , If the smallest ones are larger than the target value , What are you looking for 
                if (nums[i] > target && nums[i] >= 0) {
    
                    break;
                }
                // i  Benchmarking 
                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  Benchmark for the second element 
                    if (j > i + 1 && nums[j] == nums[j - 1]) {
    
                        System.out.println(" The second element repeats the previous one , Skip this cycle ");
                        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(" And for " + sum);
                        if (sum == target) {
    
                            System.out.println(" Equal to the target value ");
                            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(" Less than the target , Left pointer plus ");
                        } else if ((sum > target)) {
    
                            right--;
                            System.out.println(" Greater than the target value , Right pointer subtraction ");
                        }
                    }

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