1. Title Description

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

Example 3:

Input: nums = [0]Copy the code

Tip:

  • 0 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

Second, train of thought analysis

The sum of three numbers, after reading the topic to think first, must not initiate the idea of three layers of circulation.

We can turn the sum problem into a difference problem:

Fix one of these numbers and find out if there are two numbers that add up to this fixed number that are equal to 0.

  • Sort the array first (double Pointers can be used in ordered arrays to narrow the location range)
  • Use double Pointers to deal with the sum of two numbers
  • If the sum is greater than 0, the number on the right is too large and the right pointer moves to the left
  • If the sum is less than 0, the number on the left is smaller and the left pointer moves to the right
  • Notice that repeating elements are skipped

AC code

/** * @param {number[]} nums * @return {number[][]} */ const threeSum = function(nums) {let res = [] // Nums = nums.sort((a,b)=>{return a-b}) const len = nums.length For (let I =0; i<len-2; I ++) {// left pointer j let j= I +1 // right pointer k let k=len-1 Skip the if (I > 0 && nums = = = nums [I] [I - 1]) {continue} while (j (k) {/ / three number the sum is less than zero, Left pointer forward the if (nums nums [I] + [j] + nums [k] < 0) {j++ / / handle the left pointer elements repeat case while (j < k && nums [j] = = = nums [1]) {j++}} the else If (nums[I]+nums[j]+nums[k]>0){ While (j<k&&nums[k]===nums[k+1]) {k--}} else {// Get the target number combination, Res.push ([nums[I],nums[j],nums[k]]) Skip the while (j < k && nums [j] = = = nums [1]) {j++} / / right pointer if repeated, Skip the while (j < k && nums = = = [k] nums [k + 1]) - {k}}}} / / return the result array return res};Copy the code

Four,

  • The sum of the three numbers turns the summation problem into a difference problem — fix one of the numbers and look for two of the remaining numbers that add up to the difference between the fixed number and the target number.
  • A double pointer in an ordered array simply helps us narrow down the location.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign