LeetCode Q15: 3 Sum

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:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• 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)

My solution:
O(n^2).

	class Solution {
	public:
	vector<vector<int>> threeSum(vector<int>& nums) {
	vector<vector<int> > res;
	if(nums.size()==0||nums.size()<3)
	return res;
	sort(nums.begin(), nums.end());
	for(int i=0; i<nums.size()-2; i++){
	if(i>=1&&nums[i]==nums[i-1])
	continue;
	int sum = 0-nums[i];
	int p0=i+1, p1=nums.size()-1;
	while(p0<p1){
	if(p0>i+1&&nums[p0]==nums[p0-1]){
	p0++;
	continue;
	}
	if(p1<nums.size()-1&&nums[p1]==nums[p1+1]){
	p1--;
	continue;
	}
	int tmp = nums[p0]+nums[p1];
	if(tmp==sum){
	vector<int> v={nums[i], nums[p0], nums[p1]};
	res.push_back(v);
	p0++; p1--;
	}else{
	if(tmp<sum)
	p0++;
	else
	p1--;
	}
	}
	}
	return res;
	}
	};

view raw Q153sum.cpp hosted with ❤ by GitHub