https://oj.leetcode.com/problems/3sum/

Q15.cpp

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> > result;
        unordered_map<int, vector<vector<size_t> > > lookup;
        int prev_i = 0; // avoid duplication
        for (size_t i = 0; i < num.size(); i++) {
            if (i > 0 && num[i] == prev_i) continue;
            prev_i = num[i];
            int prev_j = 0;
            for (size_t j = i + 1; j < num.size(); j++) {
                if (j > (i+1) && num[j] == prev_j) continue;
                prev_j = num[j];
                lookup[num[i]+num[j]].push_back(vector<size_t>{i, j});
            }
        }

        bool flag = false; // at least one element has been pushed to result
        for (int i = (int)num.size() - 1; i >= 0; i--) {
            if (flag && prev_i == num[i]) continue;
            if (lookup.count(-num[i])) {
                for (auto t : lookup[-num[i]]) {
                    /* 1. ensure that one element will not be used twice in a single 3Sum
                     * 2. ensure that the elements in the result will be sorted by ascending order (since we sorted the array in the beginning) */
                    if (t[0] < t[1] && t[1] < i) {
                        result.push_back(vector<int>{num[t[0]], num[t[1]], num[i]});
                        prev_i = num[i];
                        flag = true;
                    }
                }
            }
        }
        return result;
    }
};