Slow C solution but without cheating, no hash table, no memory consumption


  • 0
    C
    int* twoSum(int* nums, int numsSize, int target) {
        int i,j,k;
        int *nums_needed = (int*)malloc(sizeof(int)*numsSize);
        int *nums_needed_in = (int*)malloc(sizeof(int)*numsSize);
        int* indices = (int*)malloc(sizeof(int)*2);
        for(i=0,j=0;i<numsSize;i++){
        	for(k=0;k<j;k++){
        		if(nums[i]==nums_needed[k]){
        			indices[0] = nums_needed_in[k]+1;
        			indices[1] = i+1;
        			goto out;
        		}
        	}
        	nums_needed[j] = target - nums[i];
        	nums_needed_in[j] = i;
        	j++;
        }
        out:
        return indices;
    }

  • 0
    W

    Does this solution pass? I'm doing something similar with a hash table instead of the inner loop, which theoretically should be faster, but it exceeds the time limit.

    Edit: Never mind. I optimized it a bit and it passed.


  • 0
    S

    I don't think the array 'nums_needed_in' is necessary since the index j always holds the same value as index i.

    But I'm still amazed how this solution could pass as its time complexity is O(n^n).


  • 0
    C

    lol magical. But as I said, slow, no cheating.


Log in to reply
 

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