C 3ms O(n) soln


  • 0
    A

    Only drawback I can think of is the space requirement. A input array like [0, 1, 2, 10000] will have a large memory requirement as it scales of the largest number. Any critiques?

    int hash(int num, int max){
        return num + abs(max);
    }
    
    int maxnum(int* nums, int target, int numsSize){
        int i;
        int max = abs(target);
        
        for(i = 0; i < numsSize; i++){
            int cur = abs(nums[i]);
            if(max < cur){
                max = cur;
            }
        }
        return max;
    }
     
    int* twoSum(int* nums, int numsSize, int target) {
        int i;
        int max = maxnum(nums, target, numsSize);
        int size = ((max + 1) * 2);
        int arr[size];
        int* ret = malloc(sizeof(int) * 2);
        
     
        for(i = 0; i < size; i++){
            arr[i] = -1;
        }
    
        for(i = 0; i < numsSize; i++){
            int num = nums[i];
            
            if(abs(num) <= abs(max)){
                int comp = target - num;
                int icomp = arr[hash(comp, max)];
                
                if(icomp > -1){       //success
                    ret[0] = icomp;
                    ret[1] = i;
                    return ret;
                    
                }else{
                    arr[hash(num, max)] = i;
                }
            }
        }
        
        ret[0] = -1;
        ret[1] = -1;
        return ret;
    }
    

Log in to reply
 

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