leet15.cpp

/*
http://leetcode.com/onlinejudge#question_15
refer:http://en.wikipedia.org/wiki/3SUM
keyword :hash
*/
class Solution
{
public:
    vector<vector<int> > threeSum(vector<int> &num)
    {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> ans;
        sort(num.begin(), num.end());
        int sz = num.size();
        int i = 0, j = 1, k = sz - 1;

        initset();
        for (i = 0; i < sz - 2; ++i)
        {
            j = i + 1;
            k = sz - 1;

            while (j < k )
            {
                if (num[i] + num[j] + num[k] == 0)
                {
                    string str = convertstring(num[i], num[j], num[k]);
                    if (query(str) == 0)
                    {

                        ans.push_back(vector<int> {num[i], num[j], num[k]});
                        insertset(str);
                    }

                    int t = j;
                    while (t < k && num[t] == num[j])
                    {
                        ++t;
                    }
                    j = t;
                }
                else if (num[i] + num[j] + num[k] > 0)
                {
                    --k;
                }
                else
                {
                    ++j;
                }
            }

        }
        return ans;
    }
    void initset()
    {
        hset.clear();
    }
    string convertstring(int a, int b, int c)
    {
        char num1[100];
        sprintf(num1, "%d%d%d", a, b, c);
        return string(num1);
    }
    int query(const string& str)
    {
        return hset.count(str);
    }
    void insertset(const string& str)
    {
        hset.insert(str);
    }
    unordered_set<string> hset;
};