题解 | #三数之和#

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

        int n = num.size();
        if (n < 3) return {};
        for (int i = 0; i < n; i++) {
            vector<vector<int> > tmp;
            tmp = twosum(num, -num[i]);
            if (int s = tmp.size() > 0) {
                for (auto v : tmp) {
                    auto p = find(v.begin(), v.end(), i);
                    if (p != v.end())
                        continue; //已经包含改下标，同一个值不能使用两次
                    else {
                        v.push_back(i);
                        sort(v.begin(), v.end());
                        res.push_back(v);
                    }

                }
            }
        }

        for (auto& i : res) {
            for (auto& v : i) {
                v = num[v];//下标改为值
            }
            sort(i.begin(), i.end());
        }
        sort(res.begin(), res.end() );
        res.erase(unique(res.begin(), res.end()), res.end());//去重
        return res;

    }
    vector<vector<int> > twosum(vector<int>& nums, int target) {
        int n = nums.size();
        if (n < 2) return {};
        unordered_map<int, int> map;
        vector<vector<int> > res;
        for (int i = 0; i < n; i++) {
            int tmp = target - nums[i];
            vector<int> temp;
            if (map.find(tmp) == map.end()) {
                map[nums[i]] = i;
            } else {
                //为方便去重，不直接返回值返回下标
                temp.push_back(i);
                temp.push_back(map[tmp]);
                res.push_back(temp);
            }
        }

        return res;
    }
};