给定一个包含 n 个整数的数组
nums，判断nums中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意
答案中不可以包含重复的三元组。
1
2
3
4
5
6
7
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
分析
题目需要我们找出三个数且和为 0 ，那么除了三个数全是 0 的情况之外，肯定会有负数和正数，所以一开始可以先选择一个数，然后再去找另外两个数，这样只要找到两个数且和为第一个选择的数的相反数就行了。也就是说需要枚举 a 和 b ，将 c 的存入 map 即可。
需要注意的是返回的结果中，不能有有重复的结果。这样的代码时间复杂度是 O(n^2)。在这里可以先将原数组进行排序，然后再遍历排序后的数组，这样就可以使用双指针以线性时间复杂度来遍历所有满足题意的两个数组合。
代码实现
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
45
46
47
48
func threeSum(_ nums: [Int]) -> [[Int]] {
var nums = nums.sorted(by: <) // 先排序数组
var result = [[Int]]()
if nums.count <= 2 {
return result
}
for i in 0...nums.count - 3 {
if i == 0 || nums[i] != nums[i - 1] {
let remain = -nums[i] // 找出两个数判断是否跟remain相等，如果相等那么两个数跟nums[i]和为0
var left = i + 1
var right = nums.count - 1
while left < right {
if nums[left] + nums[right] == remain {
var temp = [Int]()
temp.append(nums[i])
temp.append(nums[left])
temp.append(nums[right])
result.append(temp)
repeat {
left += 1
} while (left < right && nums[left] == nums[left - 1]) // 排除此时left重复的值
repeat {
right -= 1
} while (left < right && nums[right] == nums[right + 1]) // 排除right重复的值
} else if nums[left] + nums[right] < remain { // 左边数值小，需要left向右移动
repeat {
left += 1
} while (left < right && nums[left] == nums[left - 1])
} else {
repeat {
right -= 1
} while (left < right && nums[right] == nums[right + 1])
}
}
}
}
return result
}