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 else 16 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<vector<int> > threeSum(vector<int> &array) { 45 46 int n = array.size(); 47 48 sort(array.begin(), array.end()); 49 50 vector<vector<int>> 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<c) 61 { 62 if(array[a] + array[b]+ array[c] == 0) 63 { 64 vector<int> 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 ones 72 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 else 78 c--; 79 } 80 a++; 81 // skip the duplicate ones 82 while (array[a] == array[a-1] && a < n-2) a++; 83 } 84 85 86 87 return result; 88 } 89 };
[LeetCode] 3Sum,布布扣,bubuko.com
原文：http://www.cnblogs.com/diegodu/p/3794105.html