15. 3Sum

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

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

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void*a,const void*b)  {return *(int*)a-*(int*)b;}


/** 
 * Return an array of arrays of size *returnSize. 
 * Note: The returned array must be malloced, assume caller calls free(). 
 */  
int**  
threeSum(int* nums, int numsSize, int* returnSize){  
    if (numsSize <= 0) return NULL;  
    int total = 64;  
    int size = 0;  
    int i,start,end,sum;  
    int ** result = (int **)malloc(sizeof(int *) * total);  
  
    for(i = 0 ;i< total; i++){  
        result[i] = (int *)malloc(sizeof(int)* 3);  
    }  
    qsort(nums, numsSize, sizeof(int), cmp);  
      
    for(i = 0; i < numsSize-2; ++i){  
        
        if(nums[i] > 0)
            break;
        if(i > 0 && nums[i] == nums[i-1]){  
            continue;  
        }  

        start = i + 1;  
        end = numsSize - 1;  
        while(start < end){  
            sum = nums[i] + nums[start] + nums[end];  
            if(sum == 0){  
                if(size > 0 && result[size-1][0] == nums[i] &&  
                   result[size-1][1] == nums[start] && result[size-1][2] == nums[end]){  
                    ++start;  
                    --end;  
                    continue;  
                }  
                result[size][0] = nums[i];  
                result[size][1] = nums[start];  
                result[size][2] = nums[end];  
                size++;  
                  
                if(size == total){  
                    total <<= 1;  
                    int t;  
                    result = (int **)realloc(result,sizeof(int *) * total);  
                    for(t = size; t < total; ++t)  
                        result[t] = (int *)malloc(sizeof(int) * 3);  
                }  
                ++start;  
                --end;  
            } else if(sum > 0){  
                --end;  
            }else{  
                ++start;  
            }  
        }  
    }  
      
    *returnSize = size;  
    return result;  
}