Accepted Python O(n) solution

  • 13
    class Solution:
        # @param {integer[]} nums
        # @param {integer} target
        # @return {integer[]}
        def twoSum(self, nums, target):
            scanned = {}
            for j, item in enumerate(nums, 1):
                i = scanned.get(target - item, -1)
                if i > 0:
                    return [i, j]
                scanned[item] = j

  • 0

    this is not O(n) , it's just a trick using Python's dictionary.

  • 0
    This post is deleted!

  • 2

    Well, this is O(n). Find an element in the dictionary only requires O(1) time

  • 0

    it should be return [i-1, j-1] i guess, otherwise the result will be [2, 3]

    or: for j, item in enumerate(nums):

    if you wish

Log in to reply

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