Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. http://www.leetcode.com/onlinejudge

leetcode_3sum.cpp

#include <tr1/unordered_map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector< vector<int> > ret;
        tr1::unordered_map<int, bool> flag;
        tr1::unordered_map<string, bool> used;
        char buf[64];
        vector<int>::const_iterator i, j;
        for (i = num.begin(); i != num.end(); ++i) {
            for (j = i + 1; j != num.end(); ++j) {
                int sum = *i + *j;
                if (flag.find(-sum) != flag.end()) {
                    vector<int> tmp(3);
                    tmp[0] = *i;
                    tmp[1] = *j;
                    tmp[2] = -sum;
                    sort(tmp.begin(), tmp.end());
                    sprintf(buf, "%d %d %d", tmp[0], tmp[1], tmp[2]);
                    if (used.find(buf) == used.end()) {
                        used[buf] = true;
                        ret.push_back(tmp);
                    }
                }
            }
            flag[*i] = true;
        }
        return ret;
    }
};