题目描述:
给定一个数组,要求在这个数组中找出 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
}