leetcode 15. 三数之和

题解

首先对数组进行排序,接着把三数问题变为两数问题,即遍历第一个数,找剩下的两个数;主要注意重复问题,每一个数要保证与上一次找到的数不同,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
}