My solution to Two Sum with C and JAVA


  • 1
    Y

    C is so fast that take 5ms while java take 234ms

    int *twoSum(int numbers[], int n, int target) {
        int array[100000] = {-1};
    	int temp = 0;
    	int i = 0;
    	static int result[2];
    	for(i = 0; i < n; i++)
    	{
    		array[numbers[i] + 5000] = i;
    	}
    	for(i = 0; i < n; i++)
    	{
    		temp = array[target - numbers[i] + 5000];
    		if(temp)
        		if(temp > i)
        	    {
        	        result[0] = i + 1;
        	        result[1] = temp + 1;
        	        break;
        	    }
    	}
    	return result;
    }
    

    while use java to solve this problem, i try several way to dispose of it, below is my thinking:
    first i use double for to ergodic the array, but time limited it takes O(n2)
    second i use quicksort and binsch to help , but still limited it takes O(nlgn)
    third i use Hashmap instead, it is ok to solve this, but still not to satisfy
    so the fourth is

    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int array[] = new int[100000];
    		int temp = 0;
    		for(int i = 0; i < numbers.length; i++)
    		{
    			array[numbers[i] + 5000] = i;
    		}
    		for(int i = 0; i < numbers.length; i++)
    		{
    			temp = array[target - numbers[i] + 5000];
    			if(temp > 0 && temp > i)
    				return new int[]{i + 1, temp + 1};
    		}
    		return null;
         }
    }

  • 1
    S

    Hi, I don't understand why you write temp > 0 && temp > i here, I've tried just write temp > 0 is ok


  • 0
    Y

    I don]t agree with you

    think about this: {1,3,2,4} target = 6


  • 0
    Y

    i agree with you, because the array has covered the old one, and will not occur i == temp when finding the result


  • 0
    M

    your solution how to deal with (numbers[i] < -1000000) ?
    array[numbers[i] + 5000] is error.


  • 0
    K

    couple of problems with this java solution:

    1. What if numbers > 5000 or < -5000
    2. A big waste on memory.

  • 0
    X

    I think that is a simple hash method and the number 5000 is a hypothetically large enough.


  • 0
    X

    what if change the number 10000 to 0xffffffff ?


Log in to reply
 

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