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 中了~