# How to improve this method with O(n^2)? (32ms)

• Such as the topic, thanks.

static int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}

int maximum(int *nums, int numsSize) {
int max = abs(nums[0]);
int i;
for(i=1;i<numsSize;i++) {
int cur = abs(nums[i]);
if(cur > max)
max = cur;
}
return max;
}

int** threeSum(int* nums, int numsSize, int* returnSize) {

``````int total = 64;
int **output = (int **) malloc(sizeof(int *) * total);
if(numsSize == 0)  {
*returnSize = 0;
return output;
}
qsort(nums, numsSize, sizeof(int), cmp);

int max = maximum(nums, numsSize);
int size = (max + 1) * 4;
int arr[size];
int target = 0;
int i,j;

int output_size = 0;

for(i=0;i<size;i++)
arr[i] = -1;

for(i = 0; i < numsSize; i++) {
arr[nums[i] + (max*2)] = i;
}

for(i = 0; i < total; ++i) {
output[i] = (int *)malloc(sizeof(int) * 3);
}

for(i=0;i<numsSize;) {
for(j=i+1;j<numsSize;j++) {
int temp = arr[(target - nums[i] - nums[j]) + max * 2];
if(temp > -1) {
if(temp > i && temp > j) {
// check duplicate
int isRepeat = 0;
int x;
for(x=output_size-1; x>=0; x--) {
if(output[x][0] == nums[i]
&& output[x][1] == nums[j]
&& output[x][2] == nums[temp]) {
isRepeat = 1;
break;
}
}
if(isRepeat) continue;
// end of check duplicate
output[output_size][0] = nums[i];
output[output_size][1] = nums[j];
output[output_size][2] = nums[temp];
output_size++;

if(output_size == total) {
int t;
total <<= 1;
output = (int **)realloc(output, sizeof(int *) * total);
for(t = output_size; t < total; ++t)
output[t] = (int *)malloc(sizeof(int) * 3);
}
}
}
}
i++;
}
*returnSize = output_size;
return output;
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.