# 5 lines solution o(n) use python

• ``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d={}
for i,v in enumerate(nums):
if target-v in d:
return [d[target-v],i+1]
d[v]=i+1``````

• (Invalid)

This is O(n^2),

1. A linear scan `for` loop on line `for i,v in enumerate(nums):`

2. A linear scan by `in` operator for each number on line `if target-v in d`

• If you're going to complain every time someone uses O(1) for hash table lookups in their analysis, you'll have quite a lot of complaining to do :-P

• Ha-ha true that if nums is dict. Unfortunately nums is a list which is internally an array. Check this which says the runtime of in operator - https://wiki.python.org/moin/TimeComplexity

• Huh? What are you talking about? Is your "2)" referring to the `in` of `for i,v in enumerate(nums):`?

• Oh! Sorry for not being clear. I meant `in` in `if target-v in d`

• That's what I thought, but... that's checking `d`, not `nums`. And `d` is a dict.

• Sorry my bad. Didn't see that.

• Incorrect solution

• someone plz explain what i+1 and d[v]=i+1 is used for?

• @encrypt
this question has an update in (2016/2/13): The return format had been changed to zero-based indices.

before this update, the return format was one-based indices. that's why i+1. Now just use i plz

• @sohje after the update of the question, it is incorrect. because now is zero-based while before is one-based

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