首页 > 代码库 > [LeetCode] 3Sum

[LeetCode] 3Sum

2024-07-08 16:26:58   215人阅读

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

 


联系
我们