Simple 36ms Python solution - O(n)


  • 0
    S
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            target_num_dict = {}                                # stores the expected number (target-num) and it's index
            for idx, num in enumerate(nums):
                if (target-num) in target_num_dict:             # if the target already exists in the dictionary- we're done :) 
                    return [ target_num_dict[target-num][1], idx]
                target_num_dict[num] = ( target-num , idx )     # else add the tuple to target_num_dict
            return None
    

  • 0
    L

    @Saibhavya116 I run your code 8 times, the best runtime is 52ms.

    And here is my code, the best runtime is 48ms.

    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            hash = {}
            for i, num in enumerate(nums):
                if num in hash:
                    return [hash[num], i]
                hash[target-num] = i
    

  • 0
    S

    @lxyscls: Hi, your solution is short and neat too, thanks for posting it here :), I appreciate it. I see the run time varies per each run. I ran my code just once and got it as 36ms. I did notice that with the repetitive submission of the same piece of code the time varied per each run (tested with the other solutions). But honestly I'm not sure on that part, sorry I don't have a precise answer for your question. Will try to take a screen shot from next time :). Thanks.


Log in to reply
 

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