题解 | #三数之和#

class Solution {
  public:
    vector<vector<int> > threeSum(vector<int>& num) {
        if (num.size() < 3)
            return vector<vector<int>>();
        unordered_map<int, int> occurence;
        unordered_map<int, int> max_pos;
        sort(num.begin(), num.end());
        for (int i = 0; i < num.size(); i++) {
            occurence[num[i]]++;
            if (max_pos.count(num[i]) == 0)
                max_pos[num[i]] = i;
            else
                max_pos[num[i]] = max(max_pos[num[i]], i);
        }
        int last_i = -200;
        vector<vector<int>> ret;
        for (int i = 0; i < num.size() - 1; i++) {
            if (num[i] == last_i)
                continue;
            else {
                last_i = num[i];
                int last_j = -200;
                for (int j = i + 1; j < num.size() - 1; j++) {
                    if (num[j] == last_j)
                        continue;
                    else {
                        last_j = num[j];
                        int cur_target = -num[i] - num[j];
                        if (occurence.count(cur_target) == 0)
                            continue;

                        int need = 1;
                        if (num[i] == cur_target)
                            need++;
                        if (num[j] == cur_target)
                            need++;
                        if (occurence[cur_target] >= need) {
                            if (max_pos[cur_target] > j) {
                                vector<int> cur_entry = {num[i], num[j], cur_target};
                                ret.emplace_back(move(cur_entry));
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};