# 15.M 三数之和

> Problem: [15. 三数之和](https://leetcode.cn/problems/3sum/description/)

## 思路

最简单的思路是三重循环，`first := 0; second := first + 1; third := second + 1`，然后判断合是否符合要求，符合要求则加到结果中。但是时间复杂度为O(N^3)

优化后的思路是先排序，然后每次先固定`first`的值，再用双指针分别表示`second`和`third`，`second`不断右移，`third`则先初始化为数组右边界，在结果不符合要求时不断左移（需要保证`second < third`）。

需要注意的细节是避免重复，每次开始`first`和`second`的遍历时，如果发现当前值与上一个值相同，则跳过。

## Code

```go
import "sort"

func threeSum(nums []int) [][]int {
	sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })
	var res [][]int
	for first := 0; first < len(nums)-2; first++ {
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}

		for second := first + 1; second < len(nums)-1; second++ {
			if second > first+1 && nums[second] == nums[second-1] {
				continue
			}

			third := len(nums) - 1
			for second < third && nums[first]+nums[second]+nums[third] > 0 {
				third--
			}

			if second == third {
				break
			}

			if nums[first]+nums[second]+nums[third] == 0 {
				res = append(res, []int{nums[first], nums[second], nums[third]})
			}
		}
	}

	return res
}
```

2016.1.21代码：

```go
import "sort"

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var ans [][]int
	for l := 0; l < len(nums)-2; l++ {
		if l > 0 && nums[l] == nums[l-1] {
			continue
		}

		// 第一个数已经大于0，找不到解
		if nums[l] > 0 {
			break
		}

		m, r := l+1, len(nums)-1
		for m < r {
			sum := nums[l] + nums[m] + nums[r]
			if sum == 0 {
				ans = append(ans, []int{nums[l], nums[m], nums[r]})
				for m < r && nums[m] == nums[m+1] {
					m++
				}
				for m < r && nums[r] == nums[r-1] {
					r--
				}
				m++
				r--
			} else if sum > 0 {
				r--
			} else {
				m++
			}
		}
	}

	return ans
}
```