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;
    }

  • 1
    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!

  • 0
    A

    thanks for your sharing!!!


  • 0
    K

    can anybody tell me where is wrong in my code?
    int sum,flag=0;
    int b[2];
    int i,j;
    for(i = 0; i<numsSize; i++)
    {

    for( j = i + 1;j<numsSize;j++)
    {
    	sum = nums[i]+nums[j];
    	if(sum == target)
    	{
    	flag = 1;
    	break;
    	}
    }
    	if(flag == 1)
    	{
    		b[0] = i;
    		b[1] = j;
    		return b;
    	}
    }
    
    printf("no such numbers!");
    return 0;

  • 0
    K

    I think this code isn't neat


  • 0
    L

    @kian24 b is a local variable, can not be returned, int *b = malloc(sizeof(int)*2);


  • 0
    L

    i think it did not need four array, just one will be ok, after get the maxPosiNum and minNegaNum, all numbers translate into 0 ~ (maxPosiNum - minNegaNum), and use the hashtable idea, just while do-loop;

    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;
        int i;
        for(i=0;i<numsSize;i++){
            if(nums[i]>maxPosiNum)
                maxPosiNum=nums[i];
            else if(nums[i]<minNegaNum)
                minNegaNum=nums[i];
        }
       
        int* bitMap = malloc(sizeof(int)*(maxPosiNum - minNegaNum));
        memset(bitMap, 0, (maxPosiNum - minNegaNum+1);
     
        int lookforNum=0;
        int k;
        for(k=0;k<numsSize;k++){
            lookforNum=target-nums[k];
            if(lookforNum>=minNegaNum&&lookforNum<=maxPosiNum){
                if(bitMap[lookforNum-minNegaNum]>0){
                    returnSize[0]=bitMap[lookforNum-minNegaNum] - 1;
                    returnSize[1]=k;
                    break;
                } else {
                 	bitMap[nums[k]-minNegaNum] = k +1;
                }
            }
        }
        return returnSize;
    }
    

Log in to reply
 

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