4ms accepted solution with C


  • 22
    K
    /**
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int* twoSum(int* nums, int numsSize, int target) {
        int *returnSize = malloc(sizeof(int)*2);
        returnSize[0]=returnSize[1]=0;
        int maxPosiNum=0;
        int minNegaNum=0;
        
        for(int i=0;i<numsSize;i++){
            if(nums[i]>maxPosiNum)
                maxPosiNum=nums[i];
            else if(nums[i]<minNegaNum)
                minNegaNum=nums[i];
        }
        
        int PosiArr[maxPosiNum+1];
        int PosiArr1[maxPosiNum+1]; //if the number appears more than once, then put it in this array
        int NegaArr[-minNegaNum+1];
        int NegaArr1[-minNegaNum+1];
        memset(PosiArr,0,sizeof(int)*(maxPosiNum+1));
        memset(PosiArr1,0,sizeof(int)*(maxPosiNum+1));
        memset(NegaArr,0,sizeof(int)*(-minNegaNum+1));
        memset(NegaArr1,0,sizeof(int)*(-minNegaNum+1));
        for(int j=0;j<numsSize;j++){
            if (nums[j]>=0) {
                (PosiArr[nums[j]]>0)?(PosiArr1[nums[j]]=j+1):(PosiArr[nums[j]]=j+1);
            }
            else{
                (NegaArr[-nums[j]]>0)?(NegaArr1[-nums[j]]=j+1):(NegaArr[-nums[j]]=j+1);
            }
        }
        int lookforNum=0;
        for(int k=0;k<numsSize;k++){
            lookforNum=target-nums[k];
            if(lookforNum>=minNegaNum&&lookforNum<=maxPosiNum){
                if(lookforNum>=0&&PosiArr[lookforNum]>0&&lookforNum!=nums[k]){
                    returnSize[0]=(k+1<PosiArr[lookforNum])?k+1:PosiArr[lookforNum];
                    returnSize[1]=(k+1>PosiArr[lookforNum])?k+1:PosiArr[lookforNum];
                    break;
                }
                else if(lookforNum<0&&NegaArr[-lookforNum]>0&&lookforNum!=nums[k]){
                    returnSize[0]=(k+1<NegaArr[-lookforNum])?k+1:NegaArr[-lookforNum];
                    returnSize[1]=(k+1>NegaArr[-lookforNum])?k+1:NegaArr[-lookforNum];
                    break;
                }
                else if(lookforNum>=0&&PosiArr1[lookforNum]>0&&lookforNum==nums[k]){
                    returnSize[0]=PosiArr[lookforNum];
                    returnSize[1]=PosiArr1[lookforNum];
                    break;
                }
                else if(lookforNum<0&&NegaArr1[-lookforNum]>0&&lookforNum==nums[k]){
                    returnSize[0]=NegaArr[-lookforNum];
                    returnSize[1]=NegaArr1[-lookforNum];
                    break;
                }
            }
        }
        return returnSize;
    }

  • 0
    S

    this code is very efficient !excellent!


  • 0
    L

    i think there is no need to compare k+1 and PosiArr[lookforNum],k+1 is definitely little than PosiArr[lookforNum]


  • 0
    D

    can you explain you code . what is the main idea behind it?


  • 2
    L

    I don't know why k+1, and submit with wrong answer, this is my revise, and accepted in 3ms:

    int* twoSum(int* nums, int numsSize, int target) {
        int *returnSize = malloc(sizeof(int)*2);
        returnSize[0]=returnSize[1]=0;
        int maxPosiNum=0;
        int minNegaNum=0;
        
        for(int i=0;i<numsSize;i++){
            if(nums[i]>maxPosiNum)
                maxPosiNum=nums[i];
            else if(nums[i]<minNegaNum)
                minNegaNum=nums[i];
        }
        
        int PosiArr[maxPosiNum+1];
        int PosiArr1[maxPosiNum+1]; //if the number appears more than once, then put it in this array
        int NegaArr[-minNegaNum+1];
        int NegaArr1[-minNegaNum+1];
        memset(PosiArr,0,sizeof(int)*(maxPosiNum+1));
        memset(PosiArr1,0,sizeof(int)*(maxPosiNum+1));
        memset(NegaArr,0,sizeof(int)*(-minNegaNum+1));
        memset(NegaArr1,0,sizeof(int)*(-minNegaNum+1));
        for(int j=0;j<numsSize;j++){
            if (nums[j]>=0) {
                (PosiArr[nums[j]]>0)?(PosiArr1[nums[j]]=j+1):(PosiArr[nums[j]]=j+1);
            }
            else{
                (NegaArr[-nums[j]]>0)?(NegaArr1[-nums[j]]=j+1):(NegaArr[-nums[j]]=j+1);
            }
        }
        int lookforNum=0;
        for(int k=0;k<numsSize;k++){
            lookforNum=target-nums[k];
            if(lookforNum>=minNegaNum&&lookforNum<=maxPosiNum){
                if(lookforNum>=0&&PosiArr[lookforNum]>0&&lookforNum!=nums[k]){
                    returnSize[0]=k;
                    returnSize[1]=PosiArr[lookforNum]-1;
                    break;
                }
                else if(lookforNum<0&&NegaArr[-lookforNum]>0&&lookforNum!=nums[k]){
                    returnSize[0]=k;
                    returnSize[1]=NegaArr[-lookforNum]-1;
                    break;
                }
                else if(lookforNum>=0&&PosiArr1[lookforNum]>0&&lookforNum==nums[k]){
                    returnSize[0]=k;
                    returnSize[1]=PosiArr1[lookforNum]-1;
                    break;
                }
                else if(lookforNum<0&&NegaArr1[-lookforNum]>0&&lookforNum==nums[k]){
                    returnSize[0]=k;
                    returnSize[1]=NegaArr1[-lookforNum]-1;
                    break;
                }
            }
        }
        return returnSize;
    }
    

  • 0
    F

    Can this program really be compiled? maxPosiNum and minNegaNum are variables , so we can not use them as the sizes to create the arrays

    int PosiArr[maxPosiNum+1];
    int PosiArr1[maxPosiNum+1]; //if the number appears more than once, then put it in this array
    int NegaArr[-minNegaNum+1];
    int NegaArr1[-minNegaNum+1];
    

  • 0
    F

    @flyerCheng
    This is variable-length arrays which are allowed in C99.
    But variable-length arrays are subsequently relegated in C11 to a conditional feature which implementations are not required to support.


  • 1
    N

    @KarlBaoJJJ But what if the maximum and the minimum is of a big absolute value, let the maximum be 2^31, and suppose an integer takes 4 bytes, a NegaArr takes up to 2^33 bytes = 2^3 Gigabytes. The code might not work for such cases.


  • 0
    M

    @daben hash find


  • 0
    C

    @KarlBaoJJJ can you explain your code?


  • 0
    Y

    @daben who know?


  • 0
    M

    in gcc 5.2.1 -std=c99
    "memset(NegaArr1,0,sizeof(int)*(-minNegaNum+1));"
    memset with a negative length always cause segment fault?


  • 0
    J
    This post is deleted!

Log in to reply
 

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