6ms C solution with O(nlogn + n) Time and O(n) Space


  • 3

    more codes see: https://github.com/lightmen/leetcode.git

    struct node {

    int val;
    int index;
    

    };

    static int cmp(const void *a, const void *b)
    {

    return ((struct node *)a)->val - ((struct node *)b)->val;
    

    }

    int* twoSum(int* nums, int numsSize, int target) {

    int *ret;
    struct node *head;
    int i,j;
    int sum;
    
    ret = (int *)malloc(sizeof(int) * 2);
    head = (struct node *)malloc(sizeof(struct node) * numsSize);
    for(i = 0; i < numsSize; ++i){
        head[i].index = i + 1;
        head[i].val = nums[i];
    }
    
    qsort(head,numsSize,sizeof(struct node),cmp);
    
    i = 0;
    j = numsSize - 1;
    while(i < j){
        sum = head[i].val + head[j].val;
        if(sum == target){
            ret[0] = head[i].index < head[j].index ? head[i].index : head[j].index;
            ret[1] = head[i].index >= head[j].index ? head[i].index : head[j].index;
            break;
        }else if(sum > target){
            --j;
        }else{
            ++i;
        }
    }
    
    return ret;
    

    }


Log in to reply
 

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