15.M 三数之和

Problem: 15. 三数之和

思路

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

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

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

Code

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
}