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)

 

分析：先排序，然后取出一个数后，在余下的数中找其他两个，即2sum，另外注意，由于题目中指定了unique，不能有重复，所以在b++，c--，a++时都要对重复情况做处理。

 

PS；其实直接使用系统的sort就行，我这里实现了一个mergeSort，算是练手吧。。 

PSPS: 在对mergeSort说两句，在mergeSort中，有条件判断 if(low < high)， 但low>= high时，就返回了，即一个元素时就什么也不做，然后执行merge()函数，就自定向上完成了排序。。

 

1 class Solution { 2      3     void merge(int* array, int low, int mid, int high) 4     { 5         int *newArray = (int*)malloc(sizeof(int)* (high-low +1)); 6          7         int i = low, j = mid+1, k = 0; 8          9         while(i <= mid && j <= high)10         {11             if(array[i] < array[j])12             {13                 newArray[k++] = array[i++];14             }15             else16                 newArray[k++] = array[j++];17         }18         19         while(i <= mid)20             newArray[k++] = array[i++];21             22         while(j<=high)23             newArray[k++] = array[j++];24             25         for(i = low; i<= high; i++)26             array[i] = newArray[i];27             28         free(newArray);29     }30     31     void mergeSort(int* array, int low, int high)32     {33         if(low < high)34         {35             int mid = (low + high)/2;36         37             mergeSort(array, low, mid);38             mergeSort(array, mid+1, high);39             merge(array, low, mid, high);40         }  41     }42     43 public:44     vector
     
      
        > threeSum(vector
       
         &array) {45         46         int n = array.size();47         48         sort(array.begin(), array.end());49         50          vector
        
         
          > result;51         52         //mergeSort(array, 0, n-1);53         54         int a, b , c;55         56         for(a = 0; a < n-2; )57         {58             b = a +1;59             c = n-1;60             while(b
          

temp;65 temp.push_back(array[a]);66 temp.push_back(array[b]);67 temp.push_back(array[c]);68 result.push_back(temp);69 // this is very important b++ and c--70 71 //skip the dupliate ones72 do {b++;} while(array[b] == array[b-1] && (b < n-1));73 do {c--;} while(array[c] == array[c+1] && (c > a));74 }75 else if(array[a] + array[b]+ array[c] < 0)76 b++;77 else78 c--;79 } 80 a++;81 // skip the duplicate ones82 while (array[a] == array[a-1] && a < n-2) a++;83 }84 85 86 87 return result;88 }89 };