This is the 17th day of my participation in Gwen Challenge

Topic describes

The sum of three number

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. Leetcode-cn.com/problems/le…

/ / sample 1Enter nums = [-1.0.1.2, -1, -4] Output: [[-1, -1.2], [...1.0.1]]
/ / sample 2Enter: nums = [0] output: []Copy the code

The label

Double pointer

Analysis of the problem solving

1. Double pointer

Let’s get right to it.

Determine the sum of three numbers using a double pointer plus the iterated element. Start by sorting the data from small to small. And then we go into traversal. The current traversal element is num[I], and a double pointer is used to record the elements at both ends. Num [l], num[r] calculates whether the sum of three numbers is equal0If so, it is added to the returned dataset variable res. Here we need to pay attention to the direction of the double Pointers when they are not equal. The first thing to notice is that the data set has already been sorted, so the sum of the three numbers is less than0Move the left pointer and make the sum bigger until it equals0.If the sum of three is greater than0, then move the right pointer so that the sum becomes smaller until it equals0. Then the two Pointers to the data to determine whether to repeat, if repeated, skip the next check.Copy the code

Go to ！！！！！

function threeSum(nums: number[]) :number[] []{
    If there are no more than three numbers, return an empty array
    if(nums.length < 3) return []
    / / sorting
    let res: number= [] [] []let sortedNums: number [] = nums.sort((a,b) = > a - b)
    // Enter traversal
    for(let i =0; i< sortedNums.length; i++) {
        // If the current iterated element is greater than 0, then the sum of three must be greater than 0, and there is no need to continue
        if(sortedNums[i] > 0) break;
        // Skip this iteration if it is repeated
        if(i > 0  && sortedNums[i] === sortedNums[i - 1]) continue
        // Left and right Pointers
        let [l, r] = [i+1, sortedNums.length - 1]
        while (l < r) {
            const sum: number = sortedNums[i] + sortedNums[l] + sortedNums[r]
            if(sum === 0) {
                // If the sum equals 0, push it forward
                res.push([sortedNums[i], sortedNums[l], sortedNums[r]])
                // If the left pointer is the same, skip ahead to the next left pointer
                while(l < r && sortedNums[l] === sortedNums[l + 1]) l++
                // If the right pointer is the same, skip to the next right pointer
                while(l < r && sortedNums[r] === sortedNums[r - 1]) r++ 
                l++
                r--
            }
            // The dataset is already sorted, so the sum of the three numbers is less than 0, so move the left pointer and make the sum larger until the result is equal to 0
            else if (sum < 0) l++ 
            // If the sum of three numbers is greater than 0, move the right pointer and let the sum get smaller until the result is equal to 0
            else if (sum > 0) r--
        }
    }
    return res
};
Copy the code

The last

Not pigeon from today, every day an algorithm problem and published articles, first want to solve the problem group for Top100, the ninth topic finished work!!