【leetcode】15. 三数之和

给你一个包含 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