15. 三数之和

[wanyuetian]

这道题用 排序+双指针的解法更快一些

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var (
		result = make([][]int, 0)
		start, end, index, addNum int
		length = len(nums)
	)
	if length > 0 && (nums[0] > 0 || nums[length -1 ] < 0) {
		return result
	}
	for index = 1; index < length - 1; index++ {
		start, end = 0, length - 1
		if index > 1 && nums[index] == nums[index - 1]{
			start = index - 1
		}
		for start < index && end > index {
			if start > 0 && nums[start] == nums[start - 1]{
				start++
				continue
			}
			if end < length-1 && nums[end] == nums[end+1]{
				end--
				continue
			}
			addNum = nums[start] + nums[end] + nums[index]
			if addNum == 0 {
				result = append(result, []int{nums[start], nums[index], nums[end]})
				start ++
				end --
			} else if addNum > 0 {
				end--
			} else {
				start++
			}
		}
	}
	return result
}

[halfrost]

@wanyuetian 是的，你提供的这个解法是最优解。我当时给出这个解法，是把 XXX SUM 这一类的题都用同一个套路解决的。

你的解法已经更新到 LeetCode Cookbook 中了~