Leetcode--3Sum

Problem Description:

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)

  分析：题目要求把所有可能的集合都找出来，因此想到的就是首先将数组排序，然后利用两重循环依次选出两个数字a和b，然后在剩下的数字中查找是否存在c，具体实现用到了upper_bound函数找到比当前数大的第一个数，去掉重复循环的情况，然后用find函数查找c是否存在，存在则将三个数记录下来。具体代码如下：

  class Solution {
  public:
      vector
      
        > threeSum(vector
       
         &num) { vector
        
          > results; if(num.size()<3) return results; vector
         
           subset; sort(num.begin(),num.end()); vector
          
           ::iterator p=num.begin(),q,flag; while(p<(num.end()-2)) { q=p+1; while(q