Hash - 18. Sum of four numbers

1 Title Description

18. Sum of four numbers

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 .

2 Title Example

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

3 Topic tips

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

4 Ideas

Sort + Double pointer

The simplest way is to enumerate all quaternions in a quadruple loop , Then the hash table is used for de duplication , Get the final answer that does not contain duplicate quads . Let's say the length of the array is n, In this method , The time complexity of enumeration is O(n4), The time complexity and space complexity of de duplication operation are also very high , So we need to change — Ideas . To avoid enumerating to duplicate quads , You need to ensure that the elements enumerated in each loop are not less than the elements enumerated in the previous loop , And the same element cannot be enumerated multiple times in the same loop .
In order to achieve the above requirements , You can sort arrays , And follow the following two points during the cycle :

• Every time — The subscript enumerated by a loop must be greater than the upper — Iterate through the index of the enumeration ;
• Same as — Re cycling , If the current element is the same as the previous element , Then skip the current element .

Use the above method , You can avoid enumerating to duplicate quads , But because the quadruple cycle is still used , The time complexity is still o(n4). Notice that the array has been sorted , Therefore, the double pointer method can be used to remove a double loop .

Use a double loop to enumerate the first two numbers , Then, after the double loop enumeration of the number, use the double pointer to enumerate the remaining two numbers . Suppose that the first two numbers enumerated by the double loop are in the subscript i and j, among i<j. At the beginning , The left and right pointers point to the subscript j＋1 And subscripts n―1. Calculate the sum of four numbers at a time , And do the following :

• If sum equals target, Then add the four numbers enumerated to the answer , Then move the left pointer to the right until a different number is encountered , Move the right pointer to the left until a different number is encountered ;
• If and less than target, Move the left pointer one bit to the right ;
• If and are greater than target, Move the right pointer one bit to the left .

The time complexity of enumerating the remaining two numbers with double pointers is O(n), So the total time complexity is o(n3), lower than O(n’).

Concrete implementation , You can also perform some pruning operations :

• After determining the first number , If nums[i]+ nums[i＋1]＋nums[i＋2]+ nums[i＋3] > target, Explain the remaining three numbers, no matter what value they take , The sum of four numbers must be greater than target, So quit the — Recirculation ;
• After determining the first number , If nums[i] + nums[n — 3]＋nums[n —2] + nums[n ―1]<target, Explain the remaining three numbers, no matter what value they take , The sum of four numbers must be less than target, So the first cycle goes directly to the next round , enumeration nums[i＋1];
• After determining the first two numbers , If nums[ department + nums[ij]+ numsl[j+1]+ nums[j＋2] > target, Explain the remaining two numbers at this time, no matter what value they take , The sum of four numbers must be greater than target, So exit the second cycle ;
• After determining the first two numbers , If nums[i]+ nums[j]+nums[n — 2]+nums[n ― 1]<target, Explain the remaining two numbers at this time, no matter what value they take , The sum of four numbers must be less than target, So the second cycle goes directly to the next round , enumeration nums[j+1].

5 My answer

class Solution {
    
    public List<List<Integer>> fourSum(int[] nums, int target) {
    
        List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
    
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {
    
            if (i > 0 && nums[i] == nums[i - 1]) {
    
                continue;
            }
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
    
                break;
            }
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
    
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
    
                if (j > i + 1 && nums[j] == nums[j - 1]) {
    
                    continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
    
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
    
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
    
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
    
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
    
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
    
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
    
                        left++;
                    } else {
    
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}