leetcode 15. 三数之和

题目描述

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:


[
[-1, 0, 1],
[-1, -1, 2]
]

题解

首先对数组进行排序,接着把三数问题变为两数问题,即遍历第一个数,找剩下的两个数;主要注意重复问题,每一个数要保证与上一次找到的数不同,nums[i]==nums[1-1], nums[j]==nums[j-1], nums[k]==nums[k+1]都是要跳过的

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func threeSum(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
res := make([][]int, 0)
for i := 0; i < n-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
j, k := i+1, n-1
for j < k {
sum := nums[i] + nums[j] + nums[k]
if sum > 0 {
k--
} else if sum < 0 {
j++
} else {
res = append(res, []int{nums[i], nums[j], nums[k]})
j++
k--
for nums[j] == nums[j-1] && j < k {
j++
}
for nums[k] == nums[k+1] && j < k {
k--
}
}
}
}
return res
}