[LeetCode]3Sum

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)

  
  

  class Solution {
  public:
      vector > threeSum(vector &num)  {
      std::vector > ans;
  	if(num.size() < 3) 
  	{
  		return ans;
  	}
  	sort(num.begin(), num.end());
  
  	//從左向右掃描,後兩個數一個在第一個數後邊一個開始，一個從末尾開始
  	for(int i = 0; i < num.size() - 2;)
  	{
  		for(int left = i + 1, right = num.size() - 1; left  0) 
  			{
  				right --;
  			}
  			else
  			{
  				std::vector tmp;
  				tmp.push_back(num[i]);
  				tmp.push_back(num[left]);
  				tmp.push_back(num[right]);
  				ans.push_back(tmp);
  				left ++;
  				right --;
  			}
  			while(left != i + 1 && left < right && num[left] == num[left - 1])
  			{
  				left++;
  			}
  			while(right != num.size() - 1 && left < right && num[right] == num[right + 1])
  			{
  				right--;
  			}
  		}
  		i++;
  		while(i < num.size() && num[i] == num[i - 1])
  		{
  			i++;
  		}
  	}
  	return ans;
      }
  };