5-line Python solution, hashtable, beats 90%


  • 7
    K

    Hash table, key is number, value is index.

    def twoSum(self, nums, target):
        index = {}
        for i, x in enumerate(nums):
            if target - x in index:
                return [index[target - x], i]
            index[x] = i

  • 0
    S

    Very fast solution. But, just for completeness, may I suggest something? I think this will give a wrong solution for test case of nums = [3,3,2,5], target = 8.

    This will return [2,4] instead of [1,4] as the second "3" overwrite the old index i of the first "3". So, it may need to check "if x not in index" before assigning index[x] = i.

    Leetcode may not test for this, but repeated integers are possible.


  • 0
    K

    Thanks for mentioning this, but the problem said "You may assume that each input would have exactly one solution."


  • 0
    S

    Oh, sorry. I totally forgot about that. My bad. Your solution is complete then! : )
    Thanks for sharing your solution. Appreciated.


  • 0
    K

    No problem:)


  • 0

    So good!I'm loving it!!


  • 1
    A

    A more optimized solution (40ms) built using your's:

    def twoSum(self, nums, target):
        index = {}
        for i, x in enumerate(nums):
            check = target - x
            if check in index:
                return [index[check] + 1, i + 1]
            else:
                index[x] = i

  • 0

    @cecilia3 Read the bold red "UPDATE (2016/2/13):" part.

    @ashwin1007 That's not "more optimized" but rather the opposite. It's slower. You're creating an extra variable and write it to it all the time. The 48ms and 40ms are irrevelant, that's almost exclusively the overhead time of the judge and Python, and it varies way too much to draw any conclusion from it. Try renaming the function to twoSumReal and adding this wrapper:

    def twoSum(self, nums, target):
        return max(self.twoSumReal(nums, target) for _ in range(1000))
    

    I submitted that with the original and yours three times each, the original took 1576, 1592 and 1612 ms, whereas yours took 1704, 1636 and 1640 ms. Which shows that a) only about 1.6 ms of those 40 or 48 ms are from the actual solution and b) your solution was indeed consistently slower.

    And an even better test is to run local tests (not on a busy server) like this, where your version is about 16% slower than the original (on my PC):

    nums = range(1000)
    solution = Solution()
    from timeit import timeit
    print timeit(lambda: solution.twoSum(nums, -1), number=10000)

  • 0
    This post is deleted!

  • 0

    Regarding "48 ms", have a look at my reply to ashwin1007's answer below. In short: It's pretty meaningless to post such times.


  • 0
    K

    Thanks, Stefan, I've modified the title. The absolute running time is meaningless, what matters is the percentage. Recently I've seen this Python style and it mentions "You should usually prefer functions to classes" and Stop Writing Classes. I think OJ is using class Solution(object): because it's easier to judge.


  • 0

    Well, since the percentage is computed by using the absolute running time, it's just as meaningless. If solutions take less than 2 ms and the system's overhead varies by ~20 ms, it's almost completely luck.

    Thanks for the links, I'll check them out. And yes, I suspect the OJ just uses classes because it's simpler to only support one format (for some problems, a class is appropriate). Though for Ruby, most problems want just a function and some problems want a class, don't know why that's not done for other languages.


  • -1
    Z

    I think this code have same bugs.
    Try nums=(4,4,4,4,4,4) and target=8
    Just return
    0 , 1
    1 , 2
    2 , 3
    3 , 4
    4 , 5
    But 2,5;2,4....and so on all is target.


Log in to reply
 

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