[leetcode] 18. Sum of four numbers

subject ：

Here you are n An array of integers nums , And a target value target . Please find and return the quads that meet all the following conditions and are not repeated [nums[a], nums[b], nums[c], nums[d]] （ If two Quad elements correspond to each other , It is considered that two quads repeat ）：

0 <= a, b, c, d < n
a、b、c and d Different from each other
nums[a] + nums[b] + nums[c] + nums[d] == target
You can press In any order Return to the answer .

Example 1：

 Input ：nums = [1,0,-1,0,-2,2], target = 0
 Output ：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2：

 Input ：nums = [2,2,2,2,2], target = 8
 Output ：[[2,2,2,2]]

Tips ：

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10 ^9
-10^9 <= target <= 10 ^9

Their thinking ：

I believe you have done the sum of three numbers before , So the idea of this topic , You can refer to the sum of three numbers , Use double pointer .

You can refer to it Sum of three numbers Make a comparison , What are the similarities and differences .

Because we need to use double pointers , So sorting is a must .

There is also the sum of three numbers , Sum of four numbers ...n Sum of numbers and so on , It's the same thing , This time I'll write you a n Sum of the numbers , You can recite it directly , I'll never be afraid again n The sum of the numbers .

Specific code ：

class Solution {
    
    public List<List<Integer>> fourSum(int[] nums, int target) {
    
        Arrays.sort(nums);
        if (nums.length < 4) {
    
            return new LinkedList<>();
        }
        return nSum(nums, target, 4, 0);
    }

    //  Recursive parameters ：nums, Current target value target, Number of current values n, The starting index of the current value start
    //  return n A list of numbers and , namely n Tuples 
    List<List<Integer>> nSum(int[] nums, long target, int n, int start) {
    
        //  Every layer of recursion should be created res To pass the list 
        List<List<Integer>> res = new ArrayList<>();
        //  The termination layer of recursion ：2 Sum of the numbers 
        if (n == 2) {
    
            int left = start, right = nums.length - 1;
            while (left < right) {
    
                //  prune ： Select the closed interval according to the rest [left, right] Prune the minimum and maximum values in 
                //  If from the current left,left+1 The minimum value ratio of composition target Big words , The rest left and right It's even bigger 
                //  So jump out , Traverse i+1
                int nMin = nums[left] + nums[left + 1];
                if (nMin > target) {
    
                    break;
                }
                //  And nMin Empathy 
                int nMax = nums[right] + nums[right - 1];
                if (nMax < target) {
    
                    break;
                }
                long sum = nums[left] + nums[right];
                if (sum == target) {
    
                    List<Integer> row = new LinkedList<>();
                    row.add(nums[left]);
                    row.add(nums[right]);
                    res.add(row);
                    //  duplicate removal 2： Remove the repetition of the last two values 
                    while (left < right && nums[left] == nums[++left]) ;
                    while (left < right && nums[right] == nums[--right]) ;
                } else if (sum < target) {
    
                    while (left < right && nums[left] == nums[++left]) ;
                } else {
    
                    while (left < right && nums[right] == nums[--right]) ;
                }
            }
        } 
        //  Normal recursion layer ：
        else {
    
            for (int i = start; i <= nums.length - n; i++) {
    
                //  duplicate removal 1： Remove the repetition of the current value . Comparison between current value and historical value ,i-1 Executed 
                //  Be careful , If de duplication is placed in front of the code block , Just use if continue  as well as i-1 and i In the form of ,
                //  If put in the back , Namely while i++  as well as  i and i+1 In the form of 
                if (i > start && nums[i - 1] == nums[i]) {
    
                    continue;
                }
                // sub Catch the result of recursion 
                List<List<Integer>> sub = nSum(nums, target - nums[i], n - 1, i + 1);
                // //  After the sequence returns, the operation on the current layer ：res add to sub And the current value 
                for (List<Integer> row : sub) {
    
                    row.add(nums[i]);
                    res.add(row);
                }
                //  Comparison between current value and historical value , Put it after the code block , use i and i+1, because i Executed 
                // while (i <= len - n - 1 && nums[i] == nums[i + 1]) {
    
                // i++;
                // }
            }
        }
        return res;
    }
}