题解 | #三数之和#

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
          unordered_multimap<int, int> themap;
        vector<vector<int>> res;

        //先将数组存到map中，这样将复杂度降到O(n^2)
        for (int i = 0; i < num.size(); ++i)
        {
            themap.insert(make_pair(num[i], i));
        }

        //两层循环计算nums[i]+nums[j]，并寻找nums[k]
        for (int i = 0; i < num.size(); ++i)
        {
            for (int j = i + 1; j < num.size(); ++j)
            {
                auto range = themap.equal_range(-(num[i] + num[j]));//这里返回的是一个pair
                for(auto it=range.first;it!= range.second;++it)
                {
                    if (it->second != i && it->second != j)//不能重复使用同一个索引
                    {
                        vector<int> tmpres{num[i],num[j],it->first};
                        sort(tmpres.begin(), tmpres.end());
                        res.push_back(tmpres);
                    }
                }
            }
        }

        //去重
        //排序
        sort(res.begin(), res.end(), [](const vector<int>& p1,const vector<int>& p2)->bool{
		  //按照从左到右比大小的顺序排列
                for (int i = 0; i < 3; ++i)
                {
                    if (p1[i] < p2[i])
                    {
                        return true;
                    }
                    else if(p1[i]==p2[i])
                    {
                        continue;
                    }
                    else
                    {
                        return false;
                    }
                }
                return false;
            });
        vector<vector<int>> termres;
        if(res.empty())
            return res;
	  
	  //去除相同的元素，此时相同的元素都是相邻的
        termres.push_back(*res.begin());

        for (auto it = res.begin(); it != res.end(); ++it)
        {
            if (*it != termres[termres.size() - 1])
                termres.push_back(*it);
        }
        return termres;
    }
};

这个方法在原数组中有元素大量重复的时候使用unordered_multimap的查询复杂度会变成O(n)，不再是O(1)，这样综合下来复杂度变成了O(n^3)，所以这个方法可能通不过测试