题目地址
题目描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
题解
暴力枚举
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
Set<String> existsResults = new HashSet<>();
// 枚举三个数的状态 (a, b, c)
int length = nums.length;
for (int a = 0; a < length; a ++) {
for (int b = a + 1; b < length; b ++) {
for (int c = b + 1; c < length; c ++) {
if (sumIsZero(nums[a], nums[b], nums[c])) {
List<Integer> result = Arrays.asList(nums[a], nums[b], nums[c]);
String uniqueKey = getUniqueKey(result);
if (existsResults.contains(uniqueKey)) {
continue;
}
results.add(result);
existsResults.add(uniqueKey);
}
}
}
}
return results;
}
public boolean sumIsZero(int a, int b, int c) {
return (a + b + c) == 0;
}
public String getUniqueKey(List<Integer> result) {
Collections.sort(result);
return result.toString();
}
}
时间复杂度
O(n^3)，n 为 nums 数组的长度。
上述代码执行超时。
hash 表查找
对于 a + b + c = 0
如果要同时枚举 a，b，c 三个数的状态，时间复杂度为 O(n^3)。可以怎么优化呢？
思考一下，如果我们枚举了 a，b 两个数的状态，是否可以推导出第三个数的状态呢？
a + b + c = 0 ==> a + b = -c ==> c = -(a + b)
通过上述等式我们可以从 a，b 两个数的状态推导出 c = -(a + b)，所以我们只需要枚举 a，b 两个数的状态，时间复杂度为 O(n^2)。
那么我们如何快速的知道是否存在 c = -(a + b) 的数呢？
查找时间复杂度
O(1)的是什么？答案是 hash 表。
还有一个小问题，就是我们可以先排序整个数组，这样就不需要在计算 getUniqueKey 时单独排序了。
具体代码如下所示：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
Set<String> existsResults = new HashSet<>();
Map<Integer, Integer> hash = initHash(nums);
// 排序后 a <= b <= c
Arrays.sort(nums);
// 枚举两个数的状态 (a, b)
int length = nums.length;
for (int a = 0; a < length; a ++) {
// 去掉 nums[a] 在 hash 表的数据
hash.compute(nums[a], (k, v) -> v - 1);
for (int b = a + 1; b < length; b ++) {
int c = -(nums[a] + nums[b]);
// c 如果小于 b，说明当前等式已经枚举过了
if (c < nums[b]) break;
// 去掉 nums[b] 在 hash 表的数据
hash.compute(nums[b], (k, v) -> v - 1);
if (hash.get(c) != null && hash.get(c) > 0) {
List<Integer> result = Arrays.asList(nums[a], nums[b], c);
String uniqueKey = result.toString();
if (!existsResults.contains(uniqueKey)) {
results.add(result);
existsResults.add(uniqueKey);
}
}
// 增加 nums[b] 在 hash 表的数据
hash.compute(nums[b], (k, v) -> v + 1);
}
// 增加 nums[a] 在 hash 表的数据
hash.compute(nums[a], (k, v) -> v + 1);
}
return results;
}
public Map<Integer, Integer> initHash(int[] nums) {
Map<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < nums.length; ++ i) {
int key = nums[i];
if (hash.containsKey(key)) {
hash.put(key, hash.get(key) + 1);
} else {
hash.put(key, 1);
}
}
return hash;
}
}
时间复杂度
O(n^2)，n 为 nums 数组的长度。
耗时有点长，但是通过了，说明时间复杂度是符合题意的，但是常量系数有点大。
还能怎么优化呢？
上面的单个状态计算逻辑中，使用了 map 作为 hash 表，使用了 set 作为结果去重的判断依据。
考虑等式 a + b + c = 0。
我们在上面做的优化是如下三步：
- (1) 排序后
a <= b <= c，（去重时就不需要额外排序了） - (2) 转换等式为
c = -(a + b) - (3) 通过 hash 查找是否存在
c。
双指针
如果不通过 hash 表，我们还能怎么处理呢？
可以通过如下步骤：
- (1) 排序后
a <= b <= c - (2) 转化等式为
a = -(b + c)
枚举所有的 a 需要 O(n) 的时间复杂度，我们怎么在 O(n) 的时间复杂度中同时确定所有符合条件的 b + c 呢？
因为 b <= c。
假设 b1 > b0，当 b0 + c0 == b1 + c1 时，会得到 c1 < c0 的结论。
因此，我们可以从左往右枚举 b，从有往左枚举 c 的状态。
这样，在 O(n) 的时间复杂度中就可以确定所有符合条件的 b+c。
完整代码如下所示：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
// 排序后 a <= b <= c
Arrays.sort(nums);
int length = nums.length;
for (int a = 0; a < length; a ++) {
// 因为 a <= b <= c
// 如果 a > 0，等式 a + b + c == 0 就不可能成立
if (nums[a] > 0) break;
int b = a + 1;
int c = length - 1;
while (b < c) {
int negativeA = nums[b] + nums[c];
if (negativeA == -nums[a]) {
List<Integer> result = Arrays.asList(nums[a], nums[b], nums[c]);
results.add(result);
// 同时移动 b 和 c 的指针
b++;
c--;
// 如果 b 和 b-1 的值一样，则需要向右移动 b 的指针
while (b < c && nums[b] == nums[b - 1]) {
b++;
}
// 如果 c 和 c+1 的值一样，则需要向左移动 c 的指针
while (b < c && nums[c] == nums[c + 1]) {
c--;
}
} else if (negativeA > -nums[a]) {
// 因为 a <= 0，所以 -a >= 0
// 如果 b + c > -a，说明 b+c 的值太大了
// 要减少 b+c 的值，就需要向左移动 c 的指针
c--;
} else {
// 因为 a <= 0，所以 -a >= 0
// 如果 b + c < -a，说明 b+c 的值太小了
// 要增大 b+c 的值，就需要向右移动 b 的指针
b++;
}
}
// 如果 a 和 a+1 的值一样，则需要向右移动 a 的指针
while (a+1 < length && nums[a] == nums[a + 1]) {
a++;
}
}
return results;
}
}
上述代码多了一些去重的逻辑，如：
// 如果 b 和 b-1 的值一样，则需要向右移动 b 的指针
while (b < c && nums[b] == nums[b - 1]) {
b++;
}
// 如果 c 和 c+1 的值一样，则需要向左移动 c 的指针
while (b < c && nums[c] == nums[c + 1]) {
c--;
}
和
// 如果 a 和 a+1 的值一样，则需要向右移动 a 的指针
while (a+1 < length && nums[a] == nums[a + 1]) {
a++;
}
缩减了常量系数后，耗时大大减少。
