给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
通过次数28
奇奇怪怪的写法，时间复杂度O(N2) 最终有个用例超时了。
image.png
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
stable_sort(nums.begin(), nums.end());
set<std::string> filterset;
vector<vector<int>> ret;
map<int,int> num_map;
for (int i : nums) {
if (num_map.find(i) == num_map.end()){
num_map[i] = 0;
}
num_map[i]++;
}
for (int i = 0; i < nums.size(); i++) {
for (int j = i+1; j < nums.size() ; j++ ){
int resval = 0 - nums[i] - nums[j];
if (num_map.find(resval) != num_map.end()){
int res_match_cnt = 1; // 记录该元素出现了几次
if (resval == nums[i]) {
res_match_cnt++;
}
if (resval == nums[j]){
res_match_cnt++;
}
if (num_map[resval] >= res_match_cnt){
//cout << "3 num = " << nums[i] << " " << nums[j] << " " << resval << endl;
vector<int> new_vec = {nums[i],nums[j],resval};
stable_sort(new_vec.begin(), new_vec.end());
std::string filter_str = to_string(new_vec[0]) + " " + to_string(new_vec[1]) + " " + to_string(new_vec[2]);
//cout << "filter_str = " << filter_str << endl;
bool if_new = filterset.insert(filter_str).second;
if (if_new)
{
ret.push_back(new_vec);
}
//cout << "ret.size = " << ret.size() << endl;
}
}
}
}
return ret;
}
};
稍微改了下，还是过了
image.png
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
stable_sort(nums.begin(), nums.end());
set<std::string> filterset;
vector<vector<int>> ret;
map<int,int> num_map;
for (int i : nums) {
if (num_map.find(i) == num_map.end()){
num_map[i] = 0;
}
num_map[i]++;
}
// 0 单独判断。
if (num_map.find(0) != num_map.end() && num_map[0] >= 3){
vector<int> new_vec = {0,0,0};
ret.push_back(new_vec);
}
for (int i = 0; i < nums.size(); i++) {
for (int j = i+1; j < nums.size() ; j++ ){
int resval = 0 - nums[i] - nums[j];
if (nums[i] == 0 && nums[j] == 0) {
continue;
}
if (num_map.find(resval) != num_map.end()){
int res_match_cnt = 1; // 记录该元素出现了几次
if (resval == nums[i]) {
res_match_cnt++;
}
if (resval == nums[j]){
res_match_cnt++;
}
if (num_map[resval] >= res_match_cnt){
//cout << "3 num = " << nums[i] << " " << nums[j] << " " << resval << endl;
vector<int> new_vec = {nums[i],nums[j],resval};
stable_sort(new_vec.begin(), new_vec.end());
std::string filter_str = to_string(new_vec[0]) + " " + to_string(new_vec[1]) + " " + to_string(new_vec[2]);
//cout << "filter_str = " << filter_str << endl;
bool if_new = filterset.insert(filter_str).second;
if (if_new)
{
ret.push_back(new_vec);
}
//cout << "ret.size = " << ret.size() << endl;
}
}
}
}
return ret;
}
};
好了，试一下正确的方法，排序+双指针，可以ac。
这里的改进点在于:
- 利用排序从小达到的特性，在已经确定第一个数的时候，确定另外两个数双指针把vector扫一遍。相比于第一种方法，遍历第二个数，查到第三个数有没有出现，时间负责一样但是性能更有。
- 更核心的是，查找第三个数有没有出现，丢失了位置信息，对于去重和数据里是否保护一个元素多次计算很麻烦。而用这个方法，在迭代 i,x,y 去重只需要一个原则：如果这个数和上一个数一致就skip。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
stable_sort(nums.begin(), nums.end());
vector<vector<int>> ret;
for (int i = 0; i < nums.size(); i++) {
// skip repeat num
if (i > 0 && nums[i] == nums[i-1]){
continue;
}
set<int> filter_set_2;
int l = i + 1, r = nums.size() - 1;
while (l < r){
// skip repeat num
if (l > i+1 && nums[l] == nums[l-1]){
l++;
continue;
}
else if (r < nums.size() - 1 && nums[r] == nums[r+1]){
r--;
continue;
}
int match_num = -nums[i];
if (nums[l] + nums[r] == match_num){
// 判断重复
vector<int> new_vec = {nums[i],nums[l],nums[r]};
ret.push_back(new_vec);
l++;
r--;
}
else if (nums[l] + nums[r] < match_num){
l++;
}
else {
r--;
}
}
}
return ret;
}
};
但是性能还是不够好。
image.png
