3Sum II

Given an array A of n integers, find all unique triplets in the array which gives the sum of zero.

The problem is a modification of the problem 3 Sum 

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]
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> result; if(nums.size() < 3) return result; for(int i = 0; i < nums.size() - 2; i++){ if(i == 0 || nums[i] != nums[i - 1]){ int j = i + 1, k = nums.size() - 1; while(j < k){ //use the approach as for 2 Sum if(nums[i] + nums[j] + nums[k] == 0){ vector<int> three; three.push_back(nums[i]); three.push_back(nums[j]); three.push_back(nums[k]); result.push_back(three); j++; k--; // skip duplicates while(j < k && nums[j - 1] == nums[j]){ j++; } // skip duplicates while(j < k && nums[k + 1] == nums[k]){ k--; } } else if(nums[i] + nums[j] + nums[k] < 0){ j++; }else{ k--; } } } } return result; } };