Title link: leetcode-cn.com/problems/3s…

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:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[1, 1, 2], [1, 1]]

  • Example 2:

Input: nums = []

Output: []

  • Tip:

0 <= nums.length <= 3000

-105 <= nums[i] <= 105

The problem solving

Optimal solution: sort first, then use the double pointer movement method, time complexity O (n)

/** * @param {number[]} nums * @return {number[][]} */ var threeSum = function(nums) {let arrSOrt = nums.sort((a,b) => a - b); // result array let result = []; for (let i = 0; i<nums.length; If (I > 0 && arrSOrt[I] === arrSOrt[i-1]) continue; let left = i + 1; let right = nums.length - 1; while(left < right) { let sum = arrSOrt[i] + arrSOrt[left] + arrSOrt[right]; if (sum === 0) { result.push([arrSOrt[i], arrSOrt[left], arrSOrt[right]]); While (left < right && arrSOrt[left] === arrSOrt[left+1]) left++; while(left < right && arrSOrt[right] === arrSOrt[right - 1]) right--; left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return result; };Copy the code

conclusion

The topic is easy to ignore to repeat, write right at once or a bit of a challenge.

Github: github.com/mengmengzp/…