LeetCode 15. 三数之和
题目描述
✅ 15. 三数之和
思路分析
排序+双指针
参考代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func threeSum(nums []int) [][]int {
var res [][]int
n := len(nums)
// 排序数组
sort.Ints(nums)
for i := 0; i < n-2; i++ {
// 跳过重复元素
if i > 0 && nums[i] == nums[i-1] {
continue
}
target := -nums[i]
left, right := i+1, n-1
for left < right {
sum := nums[left] + nums[right]
if sum == target {
res = append(res, []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 < target {
left++
} else {
right--
}
}
}
return res
}
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！