-
-
Save prehistoricpenguin/5279844 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment