This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The title

Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.

Note: Repeated triples cannot be included in the answer.

Example 1

Input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]]Copy the code

Example 2

Nums = [] Output: []Copy the code

Train of thought

The problem is to find all possible triples of 0 in a given array nums, and the triples are not repeatable

That is [1, 1, 2] and [1, 2, 1] is the same triples, and if: [nums [I], nums [j], nums [k]] = = [nums [I], nums [j], nums [k]] at least I! = I, j! = J, k! Equals K is an equation, and they are the same triplet

So the general idea is:

Violent solution

  • First, sort the nums array from smallest to largest

  • Enumerates the first element of the triad, the second element of the triad, and the third element

  • Keep the above triples that match the problem conditions

  • If nums[I + 1] is equal to nums[I], then the enumeration position I + 1, This ensures that the first element of the triad will not be repeated, and the same goes for the second element. In the process of looking for the third element, if the element that meets the requirements is found, it can directly exit the third layer loop to ensure that the third element is not repeated

  • Several conditions that end the enumeration prematurely

    • If the first element is enumerated and nums[I] > 0, the result can be returned directly (because a number greater than 0, plus any number greater than it, will be greater than 0).

    • Nums [I] + nums[j] > 0 if the first element is enumerated and the second element is initialized at j = I + 1, the result can also be returned directly

    • If nums[I] + nums[j] + nums[n-1] < 0, it indicates that the element at position j does not meet the requirements. Skip j to j + 1

The following code

    var threeSum = function(nums) {
        let ans = [], n = nums.length;
        // Sort from smallest to largest
        nums.sort((a, b) = > a - b);
        for(let i = 0; i < n - 2; i++) {
            // End enumeration 1 early
            if(nums[i] > 0) {
                return ans;
            }
            let j = i + 1;
            // End enumeration 2 early
            if(nums[i] + nums[j] > 0) {
                return ans;
            }
            for(j; j < n - 1; j++) {
                // End enumeration 3 early
                if(nums[i] + nums[j] + nums[n - 1] < 0) {
                    continue;
                }
                let k = j + 1;
                while(k < n) {
                    // Find the element in position 3 only once
                    if(nums[i] + nums[j] + nums[k] == 0) {
                        ans.push([nums[i], nums[j], nums[k]]);
                        break;
                    }
                    k++;
                }
                // The second position to remove the weight
                while(j + 1 < n - 1 && nums[j] == nums[j + 1]) { j++; }}// The first position to remove the weight
            while(i + 1 < n - 2 && nums[i] == nums[i + 1]) { i++; }}return ans;
    }
Copy the code

Sort plus double pointer

For sorted arrays, we can use a double pointer when looking for two numbers in the array that meet certain conditions, because we know exactly how the pointer moves

Optimize the above solution for finding triples, second and third elements:

  • Define a double pointer left = I + 1, right = n-1

  • Sum = nums[I] + nums[left] + nums[right]

    • Sum = = 0, will [nums [I], nums [left], nums [right]] into the results, at the same time will be left to the right on to the next is not equal to nums [left] the location of the (heavy), Move right left to the next position not equal to nums[right] and compare again

    • Sum > 0, move right to the left

    • Sum < 0, move left to right

  • Repeat the above steps

The following code

    / * * *@param {number[]} nums
     * @return {number[][]}* /
    var threeSum = function(nums) {
        let ans = [];
        nums.sort((a,b) = > {return a - b});
        const n = nums.length;
        for(var i = 0; i < n; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] === nums[i - 1]) continue;
            let left = i + 1;
            let right = n - 1;

            while(left < right) {
                const sums = nums[i] + nums[left] + nums[right];
                if(sums == 0) {
                    ans.push([nums[i], nums[left], nums[right]]);
                    while(left < right && nums[left] === nums[left + 1]) left++;
                    while(left < right && nums[right] === nums[right - 1]) right--;
                    left++;
                    right--;
                } else if(sums > 0) {
                    right--;
                } else{ left++; }}}return ans;
    };
Copy the code

summary

Complex problems, to learn to decompose; After decomposition may be double pointer 😂😂😂

LeetCode 👉 HOT 100 👉 Sum of three numbers – medium question ✅

LeetCode 👉 HOT 100 👉 Container that holds the most water – medium title ✅

LeetCode 👉 HOT 100 👉 longest loop string – medium ✅

LeetCode 👉 HOT 100 👉 The oldest string without repeating characters – medium ✅

LeetCode 👉 HOT 100 👉 add two numbers – medium ✅

LeetCode 👉 HOT 100 👉 sum of two numbers – easy question ✅