[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; } };