问题链接

题目解析

给定n个元素的数组，寻找符合 \(a+b+c=0\) 的所有 {a, b, c}。

解题思路

如果对LeetCode的第一题 还有印象的话，会发现这道题很类似，不过题目要求的结果有明显区别，本题需要求出所有符合条件的结果。

如果想复用Two Sum中的方法，可以加以转化：\(a+b = -c\)，与 \(x+y = target\)就很类似了。存在一个严重的问题——重复的结果！为了避免重复，可以想到需用使用 \(set\) 容器。由于 \(set\) 中的元素是三元素向量，想要避免重复必须使向量中三个元素有序，所以需要先将数组排序。

参考代码

class Solution {public:    vector
    
     
      > threeSum(vector
      
       & nums) {        set
       
        
         > res;        sort(nums.begin(), nums.end());        for (int k = 0; k < nums.size(); k++) {            if (nums[k] > 0) break;                        int target = 0 - nums[k];//固定最小数            int i = k + 1, j = nums.size() - 1;            while (i < j) {                if (nums[i] + nums[j] < target) ++i;                else if (nums[i] + nums[j] > target) --j;                else {                    res.insert({nums[k], nums[i], nums[j]});                    ++i; --j;                }            }        }        return vector
         
          
           >(res.begin(), res.end()); }};
          
         
        
       
      
     
    

方法改进

上述代码需要300+ms，太慢了，仔细想想，其实不用 \(set\) 容器也可以做到，先将数组排序，遍历每个数字，即先确定最小的数字，寻找另外两个数，避免重复只需要跳过相等的数字（位于相邻位置）即可。思路一模一样，这其实是对上一方法的简化，因为二者都需要排序，而排好序后相等的数字必然在相邻位置，开直接排序，不需要 \(set\)。这种改进方法只要100+ms，快了不止一点点~

参考代码

class Solution {public:    vector
    
     
      > threeSum(vector
      
       & nums) {        vector
       
        
         > res;        sort(nums.begin(), nums.end());        for (int k = 0; k < nums.size(); k++) {            if (nums[k] > 0) break;            if (k > 0 && nums[k] == nums[k - 1])//避免重复                continue;                        int target = 0 - nums[k];//固定最小数            int i = k + 1, j = nums.size() - 1;            while (i < j) {                if (nums[i] + nums[j] < target) ++i;                else if (nums[i] + nums[j] > target) --j;                else {                    res.push_back({nums[k], nums[i], nums[j]});                    while (i < j && nums[i] == nums[i + 1])//避免重复                        ++i;                    while (i < j && nums[j] == nums[j - 1])//避免重复                        --j;                    ++i; --j;                }            }        }        return res;    }};
        
       
      
     
    

相似题目

---

本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.

---