3sum解法二

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        if (num.size() < 3)
            return vector<vector<int> >();
        vector<vector<int>> result;
        for (int i = 0;i<num.size();i++)
        {
            int p = result.size();
            int target = -num[i];
            vector<int> new_num(num.begin()+i+1,num.end());
            vector<int> sub_result;
            map<int,int> mapping;
            for (int j = 0;j<new_num.size();j++)
            {
                auto iter = mapping.find(target - new_num[j]);
                if (iter != mapping.end())
                {
                    sub_result.push_back(num[i]);
                    sub_result.push_back(new_num[iter->second]);
                    sub_result.push_back(new_num[j]);
                }
                mapping[new_num[j]] = j;
                if (!sub_result.empty())
                {
                    result.push_back(sub_result);
                }
                sub_result.clear();
            }
        }
        for (auto &r:result)
        {
            sort(r.begin(),r.end());
        }
        sort(result.begin(),result.end());
        auto end_unique = unique(result.begin(),result.end());
        result.erase(end_unique,result.end());
        //ostream_iterator<int> out_inter(cout," ");
        //for (auto r : result)
        //{
            //for (auto e : r)
            //{
                //*out_inter++ = e;
            //}
            //cout<<endl;
        //}
        return result;
    }
};

舍去了的排序操作。在找到符合要求的值后,分别对子数组和result进行排序,然后unique算法将重复元素重排,并消除之

注释部分为流迭代器的练习

上一篇:【LeetCode算法题库】Day5:Roman to Integer & Longest Common Prefix & 3Sum


下一篇:leetcode 15. 3Sum