LeetCode2

题目：找出数组中的所有三元组a,b,c使得a+b+c = 0，所有的三元组不能重复

提供一个复杂度O(n²)的代码，复杂度为O(n³)会超时。

 1 int cmp(const void *a, const void *b){
 2     return *((int*)a) - *((int*)b);
 3 }
 4 
 5 int** threeSum(int* nums, int numsSize, int* returnSize) {
 6     int i,j,k;
 7     int **results = (int**)malloc(sizeof(int*)*100000);
 8     int temp[3];
 9     *returnSize = 0;
10     qsort(nums, numsSize, sizeof(int), cmp);
11     for(i=0; i<numsSize; i++){
12         j = i+1; k = numsSize-1;
13         while(j<k){
14             if(nums[j]+nums[k]<-nums[i])
15                 j++;
16             else if(nums[j]+nums[k]>-nums[i])
17                 k--;
18             else{
19                 results[*returnSize] = (int*)malloc(sizeof(int)*3);
20                 results[*returnSize][0] = nums[i];
21                 results[*returnSize][1] = nums[j];
22                 results[*returnSize][2] = nums[k];
23                 do{j++; }while(j<k && nums[j] == results[*returnSize][1]);
24                 do{k--; }while(j<k && nums[k] == results[*returnSize][2]);
25                 (*returnSize)++;
26             }
27         }
28         do{i++; }while(i<numsSize && nums[i]==nums[i-1]);
29         i--;
30     }
31     return results;    
32 }