My (short) Java solution [O(n) + HashMap!]


  • 56
    W

    Hello! At first glance, this can easily be solved through a quadratic algorithm BUT it can actually be done in linear time. The idea here is to use a map to keep track of the needed RIGHT operand in order for the sum to meet its target. So, we iterate through the array, and store the index of the LEFT operand as the value in the map whereas the NEEDED RIGHT operand is used as the key. When we do encounter the right operand somewhere in the array, the answer is considered to be found! We just return the indices as instructed. :]

    Feel free to let me know should you have any queries for me OR if this can be improved upon!

    public int[] twoSum(int[] nums, int target) {
            HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
            int len = nums.length;
            for(int i = 0; i < len; i++){
                if(tracker.containsKey(nums[i])){
                    int left = tracker.get(nums[i]);
                    return new int[]{left+1, i+1};
                }else{
                    tracker.put(target - nums[i], i);
                }
            }
            return new int[2];
        }

  • 0
    N
    This post is deleted!

  • 1
    Y

    I have a quick question regarding this solution, why is this solution passing for the following test case:

    [0, 2, 4, 0, 6] with the target = 6

    The correct answer should be [1, 5]. However with your code, it will return [4, 5], because when you try to insert a new pair with the same key, it'll replace it.

    Or there is so such requirement for this problem that [1, 5] should take precedence of [4,5], and both are accepted answers?


  • 0
    W

    Hi!

    Good catch. And yeah, I think the precedence does not matter in this scenario as long as two valid indices can be found for the problem at hand. :)


  • 0
    J

    The problem states that "each input would have exactly one solution". Your test case have three solutions: [1, 5], [4, 5], and [2, 3].


  • 0
    J

    Would you please explain why containsKey() and get() method is in O(1)?


  • 1
    W

    Hi!

    Certainly. So, I am essentially using a HashTable data structure. HashTable operations such as get and/or lookups usually take constant time. I say usually because it depends on how good the hash function is. If we have a good one, then we will probably have a high probability of getting the table elements within O(1) time. With a bad one, we could end up with O(n). In this case, I have left it up to Java to handle the indexing and therefore, I can safely say that containsKey() and get() would take ~O(1) time.

    For more information on the operations of a HashTable, feel free to check out the following links:-
    http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1
    http://stackoverflow.com/questions/15469795/why-hashmap-lookup-is-o1-i-e-constant-time

    Happy coding! :)


  • 0
    J

    Great post! Thanks a lot!


  • 0
    K

    cool, the first thought came up into my mind was to solve this problem in O(n) by HashSet, sooooooooooo close to your solution, but it didn't work. :(


  • 0
    T

    time complexity should be O(nlog(n))


  • 0
    I

    @ysimonliu This is the condition of this problem You may assume that each input would have exactly one solution, and you may not use the same element twice.


  • 0
    I

    @waisuan said in My (short) Java solution [O(n) + HashMap!]:

    tracker.put(target - nums[i], i);

    Logic problem tracker.put(target - nums[i], i);


  • 0
    E

    @THEONE10211024 Maybe in C++ to get a value takes O(logn) but in Java the average case of retrieving the value the time complexity is O(1)?


  • 0
    T

    @ysimonliu yes,you said currect! I thinking for a while I find this question.


  • 0
    J

    Great,thanks!


  • 0
    J

    @ysimonliu The problem explicitly states that there is only 1 solution.


  • 0
    R

    @waisuan why are we adding 1 to indexes before returning the answer?


Log in to reply
 

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