问题描述:
给定一个包含n个整数的数组nums
,判断数组中是否存在三个元素a
、b
、c
,使得a + b + c = 0
。同时,请找出所有和为0且不重复的三元组。
算法思路:
这是一个经典的三数之和问题。我们可以采用类似于两数之和的解法,通过双指针的方式来解决。
首先,对数组进行排序。然后,使用三个指针,分别指向数组的起始位置、当前遍历位置和末尾位置。遍历数组时,我们固定一个数,然后使用双指针来寻找其余两个数。
代码实现:
以下是使用Go语言实现的代码:
package main
import (
"fmt"
"sort"
)
func threeSum(nums []int) [][]int {
sort.Ints(nums)
N := len(nums)
ans := make([][]int, 0)
for i := 0; i < N-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
left := i + 1
right := N - 1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
ans = append(ans, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if sum < 0 {
left++
} else {
right--
}
}
}
return ans
}
func main() {
nums := []int{-1, 0, 1, 2, -1, -4}
ret := threeSum(nums)
fmt.Println(ret)
}
执行结果:
数组元素 | 0 | 1 | 2 | -1 | -1 | -4 |
---|---|---|---|---|---|---|
结果 | -1 | -1 | 2 | 0 | 1 | 4 |
如上所示,程序输出了所有和为0的三元组。
百度分享代码,如果开启HTTPS请参考李洋个人博客