求三个数和为0

题目描述：

给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

算法思路

使用双指针法：先对数组排序，然后用两个索引变量指向数组的首尾，遍历索引变量中间的元素与两个索引指向的元素和：

• 如果和大于0，尾部的索引向前移动一位，如果前面的一位和当前值相等直接跳过
• 如果和小于0，首部的索引向后移动一位，同样如果后面的一位和当前值相等直接跳过
• 如果等于0，将当前变量和收尾变量添加到结果中，首部索引向后移动一位，尾部索引向前移动一位。

代码：

func threeSum(num []int) [][]int {
    sort.Ints(num)
    start, end, index, length := 0, 0, 0, len(num)
    var (
        result = make([][]int, 0)
    )
    for index = 1; index < length-1; index++ {
        start, end = 0, length-1
        for start < index && index < end { //注意避免重复
            //重复的值跳过
            if start > 0 && (num[start] == num[start-1]) {
                start++
                continue
            }
            //重复的值跳过
            if end < length-1 && (num[end+1] == num[end]) {
                end--
                continue
            }
            sum := num[start] + num[end] + num[index]
            if sum == 0 {
                result = append(result, []int{num[start], num[index], num[end]})
                start++
                end--
            } else if sum > 0 {
                end--
            } else {
                start++
            }
        }
    }
    return result
}