This is an extension of the 2Sum problem. The idea is pretty simple (even no need to use hash). Sort the array and then starting from the first element, set two pointers left and right: one after the current element and the other at the end of the tail. If all the three elements sum to 0, then they are an answer. Add them to the result. Then you need to be careful to skip the duplicates! If you pay enough attention to the details, this problem has a fairly straightforward implementation without too many tricks.
The final code is as follows.
1 vector<vector<int>> threeSum(vector<int>& nums) { 2 vector<vector<int> > res; 3 if (nums.size() <= 2) return res; 4 sort(nums.begin(), nums.end()); 5 int l = 0, r = nums.size() - 1; 6 for (int i = 0; i < (int)nums.size() - 2;) { 7 int l = i + 1, r = nums.size() - 1; 8 while (l < r) { 9 if (nums[i] + nums[l] + nums[r] == 0) { 10 vector<int> ans(3); 11 ans[0] = nums[i]; 12 ans[1] = nums[l]; 13 ans[2] = nums[r]; 14 res.push_back(ans); 15 while (l < r && nums[l] == ans[0]) l++; 16 while (r > l && nums[r] == ans[2]) r--; 17 } 18 else if (nums[i] + nums[l] + nums[r] > 0) r--; 19 else l++; 20 } 21 i++; 22 while (i < (int)nums.size() && nums[i - 1] == nums[i]) i++; 23 } 24 return res; 25 }
