My working code for TwoSum problem


  • 6
    W

    I asked this question several days ago. I don't know why there is a time limit exceeded error here, but when i tried to use HashMap, it was accepted. If anyone wants to see the working code, I will publish it here. My pleasure to help others!

    import java.util.*;
    public class Solution {
        public void main(String[] args){
            int[] numbers = {2, 7,11,15};
            int target = 9;
            twoSum(numbers,target);
        }
       public int[] twoSum(int[] numbers, int target) {
    	HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    	int[] results = new int[2];
    	for(int i= 0; i<=numbers.length-1;i++){
    	    if(map.containsKey(numbers[i])){
    	        int index = map.get(numbers[i]);
    	        results[0] = index + 1;
    	        results[1] = i+1;
    	        break;
    	    }else{
    	        map.put(target-numbers[i],i);
    	    }
    	}
    	return results;
        }
        
    }

  • 0

    The reason you are getting Time Limit Exceeded for your other solution because it is an O(N2) brute force approach. Using Hashmap costs extra space of O(N) but it cuts down the runtime complexity to O(N), and therefore it will be accepted.


  • 0
    W

    Thanks a lot! I notice the other solution is brute force approach and the time complexity is O(N2), but I think the algorithm is correct. I wonder if I change to use another compiler instead of leetcode platform, should I get the same time limit exceeded error?


  • 0
    S

    Try {0,1,2,0} target = 0
    what's the output?


  • 0
    W

    I think the output should be [0,3]


  • 0
    S

    Index start from 1, so the answer should be [1,4]


  • 0
    W

    oh, yes, I forgot it. You are right, that is why I did results[0] = index + 1; results[1] = i+1;


  • 0
    Z

    I think use hashmap may cost a lot of space, which complexity is o(M), and M is the maximum of the list.
    I use binary search can get O(1) in space complexity ,and O(nlogn) in time complexity


  • 0
    E

    your answer maybe wrong . The key in map must be unique.When the input is like [0,3,4,0],the map will have repeated key 0,so I think your answer maybe wrong .


Log in to reply
 

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