题解 | #三数之和#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > threeSum(vector<int>& num) {
        // write code here
        // 方法一：三重遍历

        // 方法二：排序+双指针
        sort(num.begin(),num.end());
        vector<vector<int>> ans;
        if(num.size()<3)
            return ans;
        // 避免重复
        set<vector<int>> s_v;

        for(int i=0; i< num.size(); ++i)
        {
            int target = -num[i];
            int l=i+1, r=num.size()-1;
            while(l<r)
            {
                if(num[l]+num[r]==target)
                {
                    vector<int> v = {num[i],num[l],num[r]};
                    if(s_v.empty() || s_v.count(v)==0)
                    {
                        ans.emplace_back(v);
                        s_v.emplace(v);
                    }

                    // 这里不要 break，因为可能对于相同的target，有多个不同的答案
                    ++l;
                    --r;
                }
                else if(num[l]+num[r]<target)
                    ++l;
                else
                    --r;
            }
        }

        return ans;
    }
};