会超时, why? 4sum用同样的手法，却可以AC，见 https://gist.github.com/soulmachine/7957173

3Sum.cpp

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdlib>
#include <cstring>

#include <cctype>
#include <climits>

using namespace std;


// LeetCode, 3Sum
// 用一个hashmap先缓存两个数的和
// 时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& num) {
        vector<vector<int>> result;
        if (num.size() < 3) return result;
        sort(num.begin(), num.end());
        const int target = 0;

        unordered_multimap<int, pair<int, int>> cache;
        for (int a = 0; a + 1 < num.size(); ++a)
            for (int b = a + 1; b < num.size(); ++b)
                cache.insert(make_pair(num[a] + num[b], make_pair(a, b)));

        for (int c = 0; c < num.size(); ++c) {
            const int key = target - num[c];
            if (cache.find(key) == cache.end()) continue;

            auto range = cache.equal_range(key);
            for (auto k = range.first; k != range.second; ++k) {
                if (c != k->second.first && c != k->second.second) {
                    result.push_back( { num[k->second.first],
                        num[k->second.second], num[c] });
                }
            }
        }
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        return vector<vector<int> >(result.begin(), result.end());
    }
};



int main () {
//    freopen("B-small-attempt0.in", "r", stdin);
//    freopen("B-small-attempt0.out","w", stdout);
    vector<int> nums{-12,0,6,-13,-7,-15,-6,-6,-2,-14,-2,14,1,11,-12,-11,-2,-6,7,2,-5,-9,-11,-13,9,-7,-8,9,-12,-1,5,14,14,-3,8,14,-3,-13,-14,3,10,-1,2,-3,-13,-3,-7,-7,-2,-15,2,8,-9,7,2,8,7,2,2,11,-14,-8,2,7,-4,-5,7,9,-11,0,-11,-15,14,6,-11,9,-11,-3,9,-6,-11,-4,-12,-4,10,5,11,-5,-8,-2,13,-7,-3,0,-14,1,10,0,-5,6,-15,-1,6,6};
    Solution s;
    auto r = s.threeSum(nums);
    cout << r.size() << endl;
    for (auto s : r) {
        int ret = 0;
        for (auto ss : s) {
            ret += ss;
            cout << ss << " ";
        }
        cout << "=" << ret;
        cout << endl;
    }
    return 0;
}