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


  • 0
    C

    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;
    

    }


Log in to reply
 

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