LeetCode-15.三数之和

LeetCode-15 三数之和

原题链接

题目描述

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

注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

看到题目,比较朴素的方法就是逐个枚举,由 $a+b+c=0 => a+b=−c$,所以可以逐个选择 nums 中的 unique 元素作为 - c,再遍历 nums 选择符合条件的两个元素,复杂度为 $O(n^3)$。
当然,这个方法也能稍微优化一下,通过 hash 记录 nums 中出现过的所有元素,再在枚举 a 和 b 时,将 b 等价为 - c-a,于 hash 表中查询 - c-a。因为在 C++ 中一般用 STL 的 map 容器实现 hash,其内部实现基于红黑树,因此其 find() 方法复杂度为 $O(logn)$,因此整体复杂度为 $O(n^2logn)$。当然这个复杂度还是不太满足题目要求,一般都会超时,所以还需要时间复杂度更低的方法。

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
map<int, int> p;
map<vector<int>, int> p2;
vector<int> tar, tmp;
vector<vector<int>> ans;
if (nums.size() < 3) return ans;
for (int i=0; i<nums.size(); i++)
if (p.find(nums[i]) == p.end()) { p[nums[i]] = 1; tar.push_back(nums[i]); }
else p[nums[i]] += 1;
for (int i=0; i<tar.size(); i++) {
int pp = tar[i];
for (int j=0; j<tar.size(); j++) {
if (i == j && p[pp] < 2) continue;
tmp.clear();
tmp.push_back(pp);
tmp.push_back(tar[j]);
tmp.push_back(-tar[j] - pp);
sort(tmp.begin(), tmp.end());
if (p2.find(tmp) != p2.end()) continue;
p2[tmp] = 1;
map<int, int>::iterator q = p.find(-tar[j] - pp);
if (q == p.end()) continue;
if (q->first == pp && p[pp] < 2) continue;
if (q->first == tar[j] && q->second < 2) continue;
if (q->first == tar[j] && q->first == pp && q->second < 3) continue;
ans.push_back(tmp);
}
}
return ans;
}
};

因为 $a+b+c=0 => a+b=−c$,所以对于每一个 - c,都存在一个解空间 G,有 $a,b∈G$, 对于解空间 G 中的元素,若将其排序为一个有序序列 [G], 用 l 和 r 代表[G] 的左右边界元素,那么我们就可以通过比较 l + r + c 与 0 的关系在解空间序列 [G] 中寻求满足条件的(a, b)。若l + r + c < 0,则说明 l 过小,将 l 排除,并继续判断 l 的下一位元素;反之则说明 r 过大,将 r 排除,并继续判断 r 的上一位元素,通过不断地比较,最后便可以得到所有满足l + r + c = 0条件的 (a, b)。因为排序的复杂度为 $O(logn)$,枚举 - c 及在对[G] 中(a,b)的复杂度均为 $O(n)$,因此整体时间复杂度为 $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
class Solution {
public:
vector<vector<int> > threeSum(vector<int>& nums) {
vector<vector<int> > ans;
vector<int> res;
if (nums.size() < 3) return ans;
sort(nums.begin(), nums.end());
int l, r, len = nums.size();
for (int i=0; i<len; i++) {
if (nums[i] > 0) continue; //num[i]>0说明无解
if (i>0 && nums[i] == nums[i-1]) continue; //重复元素无需判断
l = i+1; r = len-1;
while(l < r) {
if (nums[i] + nums[l] + nums[r] > 0) r--;
else if (nums[i] + nums[l] + nums[r] < 0) l++;
else {
res.clear();
res.push_back(nums[i]);
res.push_back(nums[l]);
res.push_back(nums[r]);
ans.push_back(res);
do {
r--;
}while(l<r && nums[r] == nums[r+1]);
}
}
}
return ans;
}
};
0%