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.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] #include <iostream> #include <map> #include <vector> using namespace std; class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector <int >> ans; int a, b, c; int n = nums.size(); map<int, int > map1; map<int, int>::iterator iter2; if (nums.size() <= 2) return ans; for (int i = 0; i < nums.size(); i++) map1[nums[i]] ++; for (map<int, int>::iterator iter = map1.begin(); iter != map1.end(); ++iter) { a = iter->first; // 第一个数必然为负数或者0 if (a > 0) break; for (map<int, int>::iterator iter1 = iter; iter1 != map1.end(); ++iter1) { if (iter == iter1 && iter->second == 1) continue; else { b = iter1->first; iter2 = map1.find(-(a + b)); if (iter2 != map1.end()) { c = iter2->first; if (c > b || (a!= b && b == c && iter2->second >= 2) || (a == b && b == c && iter2->second >= 3)) { vector<int> ansSon = { a, b, c }; cout << a << " " << b << " " << c << endl; ans.push_back(ansSon); } } } } } return ans; } }; int main() { Solution a; vector<int> haha = { -4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6 }; a.threeSum(haha); system("pause"); return 0; }