Ideas:

In fact, the simplest idea is the violent search, the sum of three numbers, with a three-layer cycle to find, simple, but the time complexity is N ³, can not run, so we need to reduce the time complexity, so there is, sorting + double pointer solution

Method one: violent search

for(let i=0; ...). {for(let j=i+1; ...). {for(let t=j+1; ...). {if(nums[i]+nums[j]+nums[t] == 0){
       a.push(nums[i],nums[j],nums[t])
       res.push(a)
    }
  }
 }
}
return res
Copy the code

Time complexity: O(n³)

Obviously, this algorithm really isn’t optimal, so it needs to be optimized for method two

Method 2: Sort + double pointer (I think can also say three pointer?)

Ideas:

  1. If (nums.length) < 3, return an empty array
  2. Sort the array in ascending order
  3. If the first number in the array is greater than 0, the next number will also be greater than 0, so the sum of the three numbers cannot equal 0.
  4. Set three Pointers, the first to the leftmost element I, the second to the left of the I pointer, and the third to the right at the end of the array
  5. If I >0 and nums[I]==nums[i-1], skip this loop because nums[I] has been included in the answer
  6. Sum =nums[I]+nums[left]+nums[right] and move the left and right Pointers as follows
  • When sum == 0, record the combination in the answer, and move the left pointer back to skip all repeated nums[left], and move the right pointer forward to skip all repeated nums[right].
  • When sum < 0, nums[left] is shown not to be large enough, so left is moved backwards and repeated elements are skipped
  • When sum > 0, nums[right] is proved to be too large, so right is moved forward and repeated elements are skipped
var threeSum = function (nums) {
    let len = nums.length
    let res = []
    if (len < 3) return []
    nums = nums.sort((a, b) = > a - b)
    if (nums[0] > 0) return []
    let left, right
    for (let i = 0; i < len - 1; i++) {
        left = i + 1
        right = len - 1
        if (i > 0 && nums[i] == nums[i-1]) continue
        while (left < right) {
            let a = []
            if (nums[i] + nums[left] + nums[right] == 0) {
                a.push(nums[i],nums[left],nums[right])
                res.push(a)
                while (left < right && nums[left] == nums[left + 1]) {
                    left++
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--
                }
                left++
                right--
            } else if (nums[i] + nums[left] + nums[right] < 0) {
                left++
                while(left < right && nums[left] == nums[left-1]) left++
            } else {
                right--
                while(left < right && nums[right] == nums[right-1]) right--
            }
        }
    }
    return res
};
Copy the code

Time complexity: O(N²)