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.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        vector<int> tmpResult;
        
        int p,q,tmp;
        for(int i = 0 ;i<nums.size();i++)
        {
            if(i!=0&&nums[i]==nums[i-1]) continue;
            int currentNum = nums[i];
            p = i+1;
            q = nums.size()-1;
            
            while(p<q)
            {
                if(p!=i+1&&nums[p]==nums[p-1])
                {
                    p++;
                    continue;
                }
                tmp = nums[q]+nums[p];
                if(tmp==-currentNum)
                {
                    tmpResult.push_back(currentNum);
                    tmpResult.push_back(nums[q]);
                    tmpResult.push_back(nums[p]);
                    result.push_back(tmpResult);
                    tmpResult.clear();
                    p++;
                    q--;
                }else if (tmp>-currentNum)
                {
                    q--;
                }else p++;
            }
        }
        
        return result;
    }
};

two real problems .

• how to find the sum?
  change it to a 2 sum problem. when you have one value, the sum of the other two is -value.
  2 sum problem has a O(n) solution. so the final is O(n^2).

• how to remove the duplicate?
  for same values, we only use the first one and pass the rest.