3Sum

## Description

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

``````For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
``````

## Solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 `````` ``````func threeSum(nums []int) (res [][]int) { if len(nums) < 3 { return } // 从小到大排序 sort.Ints(nums) for i := 0; i < len(nums)-2; i++ { left, right := i+1, len(nums)-1 num0 := nums[i] num1 := nums[left] num2 := nums[right] // 所有数同符号则不需要继续 if (num0 > 0 && num1 > 0) || (num0 < 0 && num2 < 0) { break } for left < right { // 求和 sum := num0 + num1 + num2 if sum == 0 { // 记录满足条件的解 res = append(res, []int{num0, num1, num2}) // 跳过相同的数字避免重复解 for left < right && num1 == nums[left] { left++ } for right < left && num2 == nums[right] { right-- } } else if sum < 0 { // 和为负数则增加num1 left++ } else { // 和为正数则减小num2 right-- } num1 = nums[left] num2 = nums[right] } // 跳过相同的num0避免重复解 for i < len(nums)-2 && num0 == nums[i+1] { i++ } } return res }``````