The problem of the sum of leetcode three numbers

1. Sum of two problems

        Introduce ： Given an array of integers and a target value target, Find the sum in the array as the target value target The two integers of , And return their array subscripts , The answer cannot be repeated .

Example ：

Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .

solution 1： Violence solution , Double cycle , Violence enumeration , Time complexity O(n^2), The space complexity is O（1）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

solution 2： Use hash table , You can look for  target - x  The time complexity is reduced to from  O(N) Down to  O(1).

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

2. The sum of three problem

        Introduce ： Give you one containing n Array of integers  nums, Judge  nums  Are there three elements in a,b,c , bring  a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

Example ：

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

solution ： Sort + Double pointer

Time complexity ：O(N^2) among N  It's an array nums The length of .

Spatial complexity ：O(logN). We ignore the space to store answers , The space complexity of the extra sort is O(log N). However, we changed the input array nums, It is not necessarily allowed in practice , So it can also be seen as using an extra array to store nums Copy and sort , The space complexity is O(N).

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        //  enumeration  a
        for (int first = 0; first < n; ++first) {
            //  It needs to be different from the last enumeration 
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c  The corresponding pointer initially points to the rightmost end of the array 
            int third = n - 1;
            int target = -nums[first];
            //  enumeration  b
            for (int second = first + 1; second < n; ++second) {
                //  It needs to be different from the last enumeration 
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                //  Need assurance  b  The pointer is in  c  On the left side of the pointer 
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                //  If the pointers coincide , With  b  Subsequent additions 
                //  There will be no satisfaction  a+b+c=0  also  b<c  Of  c  了 , You can exit the loop 
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

3. The closest sum of three

        Introduce ： Give you a length of n Array of integers for  nums  and A target value  target. Please start from nums Choose three integers , Make their sum with  target  Nearest . Returns the sum of the three numbers .

It is assumed that there is only exactly one solution for each set of inputs .

Example ：

 Input ：nums = [-1,2,1,-4], target = 1
 Output ：2
 explain ： And  target  The closest and  2 (-1 + 2 + 1 = 2) .

solution ： Sort + Double pointer

Time complexity ：O(N^2) among N It's an array nums The length of . First of all, we need O(NlogN) Time to sort the array , Then in the process of enumeration , Use one cycle O(N) enumeration aa, Double pointer O(N) enumeration bb and cc, So it's a total of O(N^2)

Spatial complexity ：O(logN). Sorting requires the use of O(logN) Space . However, we changed the input array nums, It is not necessarily allowed in practice , So it can also be seen as using an extra array to store nums Copy and sort , At this time, the space complexity is O(N).

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10000000;

        //  enumeration  a
        for (int i = 0; i < n; ++i) {
            //  Guarantee that the element is not equal to the last enumeration 
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //  Using double pointer enumeration  b  and  c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                //  If and for  target  Go straight back to the answer 
                if (sum == target) {
                    return target;
                }
                //  Update the answer based on the absolute value of the difference 
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    //  If and are greater than  target, Move  c  The corresponding pointer 
                    int k0 = k - 1;
                    //  Move to the next unequal element 
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    //  If and less than  target, Move  b  The corresponding pointer 
                    int j0 = j + 1;
                    //  Move to the next unequal element 
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
}

4. Sum of four numbers

        Introduce ： 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 ：

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

solution ： Sort + Double pointer

Time complexity ：O(n^3), among nn Is the length of the array . The time complexity of sorting is O(n \log n)O(nlogn), The time complexity of enumerating quadruples is O(n^3) So the total time complexity is O(n^3+nlog n)=O(n^3)

Spatial complexity ：O(logn), among nn Is the length of the array . The space complexity is mainly determined by the extra space used for sorting . In addition, sorting modifies the input array nums, It is not necessarily allowed in practice , So it can also be seen as using an extra array to store the array nums And sort , The space complexity is O(n).  

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;
    }
}

 

summary ： The sum of the above three questions is often taken in interviews , It needs to be remembered , The above solution is roughly the same .