转载

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)

思路：

这道题和 2Sum 是类似的，2Sum 用 O(n) 的时间可以从任一数组中找到两个数的组合，此题先取一个数，再在后面的数中找 2 个数的和为所取数的相反数，容易得时间复杂度为 O(n^2) ，为简化代码编写，我们先用 O(nlogn) 的时间对数组进行排序，再进行遍历查找。想法的基本代码实现还是比较简单的，更重要的是要注意对于一些特殊情况的处理，包括：

三个数的组合可能在不同位置，但是这三个数数值是一样的，对已经出现过的组合不能重复输出；
选第一个数出来后，从剩余的数中筛选可能出现多种组合，因此找到一组可行组合时要继续往下找；
如果所选的数大于 0 ，那么可以不再继续查找了，因为排序的数组不可能出现三个大于 0 的和为 0 。

代码：

 1 /**  2  * Return an array of arrays of size *returnSize.  3  * Note: The returned array must be malloced, assume caller calls free().  4  */  5 int cmp(const void*a,const void*b)  {return *(int*)a-*(int*)b;}  6   7 int** threeSum(int* nums, int numsSize, int* returnSize) {  8     int i, **ret, left, right, j, flag = 1;  9     qsort(nums, numsSize, sizeof(int), cmp); 10     ret = malloc(sizeof(int *) * 1000); 11     *returnSize = 0; 12     ret[*returnSize] = malloc(sizeof(int) * 3); 13     for (i = 0 ; i < numsSize - 2; ++i){ 14         if (nums[i] > 0)    break; 15         ret[*returnSize][0] = nums[i]; 16         left = i + 1; 17         right = numsSize - 1; 18         while (left < right){ 19             while (nums[left] + nums[right] < -nums[i] && left < right) ++left; 20             while (nums[left] + nums[right] > -nums[i] && left < right) --right; 21             if (nums[left] + nums[right] == -nums[i] && left < right){ 22                 flag = 1; 23                 for (j = (*returnSize) - 1; j >= 0; --j){ 24                     if (nums[i] == ret[j][0] &&  25                         nums[left] == ret[j][1] &&  26                         nums[right] == ret[j][2]){ 27                         ++left; 28                         flag = 0; 29                         break; 30                     } 31                 } 32                 if (flag == 0)  continue; 33                 ret[*returnSize][1] = nums[left]; 34                 ret[*returnSize][2] = nums[right]; 35                 ++(*returnSize); 36                 ret[*returnSize] = malloc(sizeof(int) * 3); 37                 ++left; 38                 ret[*returnSize][0] = nums[i]; 39             } 40         } 41     } 42     free(ret[*returnSize]); 43     return ret; 44 }