This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the sum of 18. Four numbers in LeetCode, of medium difficulty.

Tag: double pointer, sort, sum of n numbers

Given an array nums containing n integers and a target value target, determine whether there are four elements a, B, c, and D in nums such that a + b + C + D is equal to target.

Find all quaternions that meet the condition and are not duplicated.

Note: repeated quads cannot be included in the answer.

 

Example 1:

Input: nums = (1, 0, 1, 0, 2, 2], target = 0 output: [[,1,2-2-1], [2,0,0,2], [1,0,0,1]]Copy the code

Example 2:

Input: nums = [], target = 0Copy the code

Tip:

  • 0 <= nums.length <= 200
  • –
    1 0 9 10^9     <= nums[i] <=
    1 0 9 10^9
  • –
    1 0 9 10^9     <= target <=
    1 0 9 10^9

Sort + double pointer

15. Sum of three numbers (medium) 16. Sum of nearest three numbers (medium)

Sort the array using four Pointers I, j, k, and p to represent the four numbers to be found.

  1. The first number is determined by enumeration I, the second by enumeration j, and the other two Pointers K and P move from j + 1 on the left and n-1 on the right, respectively, to the middle. Find all combinations such as nums[I] + NUMs [j] + nums[k] + nums[p] == t.

  2. Sum = nums[I] + nums[j] + nums[k] + nums[p] :

    • sum > target:pShift to the left, makesumsmaller
    • sum < target:kMoves to the right to makesumbigger
    • sum = target: Adds the combination to the result set,kMove right to continue inspection

They require that there be no duplicate elements, so we need to decrement I, j, and k. The decrement logic is to use only the first one for the same number.

Code:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int t) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) { // Determine the first number
            if (i > 0 && nums[i] == nums[i - 1]) continue; // Delete the first number.
            for (int j = i + 1; j < n; j++) { // Determine the second number
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // Select the first number from the same number.
                // Determine the third and fourth numbers
                int k = j + 1, p = n - 1;
                while (k < p) {
                
                    // Select the first number from the same number.
                    while (k > j + 1 && k < n && nums[k] == nums[k - 1]) k++; 
                    // If k skips the same element beyond p, the loop ends
                    if (k >= p) break;
                    
                    int sum = nums[i] + nums[j] + nums[k] + nums[p];
                    if (sum == t) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[p]));
                        k++;
                    } else if (sum > t) {
                        p--;
                    } else if(sum < t) { k++; }}}}returnans; }}Copy the code
  • Time complexity:i 和 jIs directly determined by enumeration, and the complexity is
    O ( n 2 ) O(n^2)     When it is settledi 和 jAfter that, it is determined by a double pointerk 和 pThat is, for each groupi 和 jIn terms of complexity,
    O ( n ) O(n)     . The total complexity is
    O ( n 3 ) O(n^3)
  • Space complexity: O(n2)O(n ^ 2)O(n2)

The last

This is the 18th article in our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.