三数之和细节

这道题看着简单，但是有细节要注意，不能有重复的三元组，我们也不能一开始的时候把重复的元素去除，如果全都是0的话，那么就删除的只剩下一个0了，显然答案是[0,0,0]

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        //nums.erase(unique(nums.begin(),nums.end()),nums.end());
       int len = nums.size();
        for(int i=0;i<len-2;i++){
            // 排除和上次一样的
            if(i>0){
                if(nums[i]==nums[i-1]) continue;
            }
            int left = -nums[i];
            for(int l=i+1,r=len-1;l!=r;l++){
                if(l>i+1 &&(nums[l]==nums[l-1])){
                    continue;
                }
                int tmp = nums[l]+nums[r];
               while(tmp>left && l<r){
                   r--;
                   tmp = nums[l]+nums[r];
               }
                if(l==r){
                    break;
                }
                if(tmp==left){
                    ans.push_back({nums[i],nums[l],nums[r]});
                }
            }
        }
        
        return ans;
        
    }
};

我们在这里再学习一个如何取出vector中重复的元素

第一正种方法是简单的利用set的特性，这部分代码比较简单，直接上code：

#include <iostream>
#include <vector>
#include <set>

using namespace std;


int main()
{
    int myints[] = {1,2,3,1,1};
    int len = sizeof(myints)/sizeof(int);
    vector<int> vec(myints, myints + len);
    set<int>s(vec.begin(), vec.end());
    vec.assign(s.begin(), s.end());
    for(int x : vec)
        cout << x << ",";
    return 0;
}

第二种方法是结合sort和unique函数

unique()函数将相邻且重复的元素放到vector的尾部 然后返回指向第一个重复元素的迭代器再用erase函数擦除从这个元素到最后元素的所有的元素。

所以可以先进行排序，这样重复元素就会堆一起了，调用unique()函数，再调用erase函数删除重复。代码见下：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main()
{
    int myints[] = {1,2,3,1,1};
    int len = sizeof(myints)/sizeof(int);
    vector<int> vec(myints, myints + len);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int x : vec)
        cout << x << ",";
    return 0;
}