Accepted Python O(n) solution


  • 13
    B
    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
    W

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


  • 0
    J
    This post is deleted!

  • 2
    Y

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


  • 0
    G

    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.