暴力解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
vector<vector<int>> r = {};
set<vector<int>> s = {};
if(len<3) return r;
for(int i=0;i<len-2;++i){
for(int j=i+1;j<len-1;++j){
for(int k=j+1;k<len;++k){
if(nums[i]+nums[j]+nums[k]==0){
vector<int> temp = {nums[i],nums[j],nums[k]};
sort(temp.begin(),temp.end());
s.insert(temp);
}
}
}
}
for(auto j:s){
r.push_back(j);
}
return r;
}
};
|
直接3层遍历，寻找到解后将vector排序，然后插入到set中，就能除去重复的vector。最后将set转换为vector输出。此法复杂度为$O(n^3)$
改进解法
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 {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
vector<vector<int>> r = {};
set<vector<int>> s = {};
if(len<3) return r;
sort(nums.begin(),nums.end());
for(int i=0;i<len-2;++i){
int target = -nums[i];
int j = i+1;
int k = len-1;
while(j<k){
if(nums[j]+nums[k]>target){
--k;
} else if(nums[j]+nums[k]<target){
++j;
} else{
vector<int> temp = {nums[i],nums[j],nums[k]};
s.insert(temp);
++j;
--k;
}
}
}
for(auto j:s){
r.push_back(j);
}
return r;
}
};
|
类似于装水的那道题，设立头尾两个指针，然后向中间靠拢。此法复杂度为$O(n^2)$.
可见设立头尾指针这个方法很能优化查询效率，值得记住。
近期评论