【leetcode】15. 三数之和
2020-07-20 本文已影响0人
章鱼哥呀
给你一个包含 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