# Here is a Python solution in O(n) time

• ``````class Solution(object):
def twoSum(self, nums, target):
if len(nums) <= 1:
return False
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i``````

• What's the time complexity of finding a key in a dict? Is it O(1)?

And you can only add target - nums[i], which is greater than 0, to the dict. This can save some time to search the dict, assuming integers are positive.

• dictionary look-up time is O(1) so you're correct on that.

• This post is deleted!

• This is a wonderful solution, but the test test is incorrect, we should modify `return [buff_dict[nums[i]], i+1]` to `return [buff_dict[nums[i] - 1], i]`, cause the index for an array is from 0 not 1.

• I copied all ur code, but it is sitll wrong answer, what is the problem?

• NVM i am wrong thx

• i think this solution while wrong in this test case:

nums = [11, 2, 2, 7, 11, 15]
target = 9

• This post is deleted!

• @sunjiankai Maybe you don't know there's an interesting algorithm called Hash.

• @sunjiankai Python dict is HashTable, so looking up a key is O(1).

• @Steven_Ge I'm seeing this same issue. Even when I copy the code here verbatim and run it through a debugger, I'm still getting an incorrect off-by-one error. Anyone else seeing this or am I completely missing something?

• Have they updated test cases to make this fail in its current state?

• This post is deleted!

• I wrote this based on your code:

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

• @Steven_Ge You are right, but a minor mistake. The modification should be return [buff_dict[nums[i]] - 1, i]

• Yes, I think the question was recently made zero-index based and not starting at 1, like in this solution. Here's the right one:

``````        if len(nums) <= 1:
return False
mydict = {}
for i in range(0, len(nums)):
if nums[i] in mydict:
return [mydict[nums[i]], i]
else:
mydict[target-nums[i]] = i

``````

• @yylucifer
`"return indices of the two numbers such that they add up to a specific target"` means
that it will return a list like [a, b] if exact item found in `nums`. I guess `nums = [11, 2, 2, 7, 11, 15]` (or `[]` or `[1]`)is not a test case.

• thank you very much

• It's easier to understand if we use the dict in the other way:

``````    def twoSum(self, nums, target):
d = {}
for i, n in enumerate(nums):
m = target - n
if m in d:
return [d[m], i]
else:
d[n] = i
``````

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