[LeetCode]4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

      For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
  
      A solution set is:
      (-1,  0, 0, 1)
      (-2, -1, 1, 2)
      (-2,  0, 0, 2)

  
  

  class Solution {
  public:
      vector > fourSum(vector &num, int target) {
       std::vector< std::vector > ans;
  	if (num.size() < 4)
  	{
  		return ans;
  	}
  	sort(num.begin(), num.end());
  
  	//排序後,從左到右掃描;中間兩個數一個從left+1,一個從right-1開始
  	for (int left = 0; left < num.size() - 3;)
  	{
  		for (int right = num.size() - 1; right > left + 2;)
  		{
  			int ml = left + 1; 
  			int mr = right - 1;
  			while (mr > ml)
  			{
  				int temp = num[left] + num[ml] + num[mr] + num[right];
  				if (temp > target)
  				{
  					mr--;
  					while(num[mr] == num[mr + 1])
  					{
  						mr--;
  					}
  				}
  				else if (temp < target)
  				{
  					ml++;
  					while(num[ml] == num[ml - 1])
  					{
  						ml++;
  					}
  				}
  				else
  				{
  					std::vector temp;
  					temp.push_back(num[left]);
  					temp.push_back(num[ml]);
  					temp.push_back(num[mr]);
  					temp.push_back(num[right]);
  					ans.push_back(temp);
  
  					mr--;
  					ml++;
  					while(ml < mr && num[mr] == num[mr + 1])
  					{
  						mr--;
  					}
  					while(ml < mr && num[ml] == num[ml - 1])
  					{
  						ml++;
  					}
  
  				}
  			}
  			right --;
  			while(left < right && num[right] == num[right + 1])
  			{
  				right--;
  			}
  		}
  		left++;
  		while(num[left] == num[left - 1])
  		{
  			left++;
  		}
  	}
  	return ans;
      }
  };