Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

Topic describes

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:
Enter nums = [-1.0.1.2, -1, -4] Output: [[-1, -1.2], [...1.0.1]]
Copy the code
  • Example 2:
Nums = [] Output: []Copy the code
  • Example 3:
Enter: nums = [0] output: []Copy the code
  • Example 4:
Enter: s =""Output:0
Copy the code
  • Tip:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
Copy the code

Train of thought

When I saw the topic, I felt very simple and directly rolled up my sleeves. I sorted the input array NUMS first, and then nested three times to find the array [A, B, C] that matched a + B + C = 0. Then I used set to remove the weight, and finally returned the result array.

function threeSum(nums) {
    nums = nums.sort()
    let result = []
    let set = new Set(a)let len = nums.length
    for(let i = 0; i < len; i++) {
        for(let j = i + 1; j < len; j++) {
            for(let z = j + 1; z < len; z++) {
                if (nums[i] + nums[j] + nums[z] == 0) {
                    let list = [nums[i], nums[j], nums[z]]
                    let str = list.toString()
                    if(! set.has(str)) { set.add(str) result.push(list) } } } } }return result
};
Copy the code

A smooth operation, results:

When I realized something was wrong, I thought hard about it and clicked on it.

Using double Pointers:

(I +1) L,(len-1)R,(len-1)R,(I +1) L,(len-1)R

  1. Sum < 0: indicates that the sum of the three values is not large enough. You can only increase the value by L+1.
  2. Sum > 0: indicates that the sum of the three digits is too large.
  3. Sum == 0: meets the condition if the adjacent values of the pointer are the same.

Finally, the array that meets the criteria is returned.

function threeSum(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) = > a - b); / / sorting
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // If the current number is greater than 0, the sum of the three numbers must be greater than 0, so end the loop
        if(i > 0 && nums[i] == nums[i-1]) continue; / / to heavy
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; / / to heavy
                while (L<R && nums[R] == nums[R-1]) R--; / / to heavy
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--; }}return ans;
}
Copy the code