Hash table solution to twoSum

I try the most to solve a twoSum problem in leetcode

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

Because nums + nums = 2 + 7 = 9, return [0, 1].

The plan:

1. brute force to iterate len(nums) O(n)
2. search for target - num[i] with a hash table O(1)

Implement

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_d = {}
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)

for i in range(len(nums)):
sub_target = target - nums[i]
nums_d[nums[i]].pop(0) #remove the fixer
result = nums_d.get(sub_target)#hash table to search

if result:
return [i, result]
return []

I strives hours for this solution but found that answer accepted but not passed Score 60.

Runtime: 60 ms, faster than 46.66% of Python3 online submissions for Two Sum. Memory Usage: 16.1 MB, less than 5.08% of Python3 online submissions for Two Sum.

I want to refactor the codes so that to achieve at least faster than 60%.

• Take care not to misuse the term refactoring when you just mean rewriting. Mar 22 '19 at 12:26

First some stylistic points

• nums_d.setdefault(nums[i], []).append(i)

The setdefault is unnecessary here, you can assign a list normally

nums_d[nums[i]] = [i]

• When you need both the index and the element use enumerate see PEP279

nums_d = {}
for i in range(len(nums)):
nums_d.setdefault(nums[i], []).append(i)

nums_d = {}
for i, e  in enumerate(nums):
nums_d[e] = [i]

• Use comprehension when possible (They use the C style looping and is considered to be faster)

nums_d = { e: [i] for i, e  in enumerate(nums) }

Hint

You loop over nums twice, but this can be done in one loop! To make it O(n)

Whenever you visit a new element in nums ->

Check if it's sum complement is in nums_d, else add the target - element to the dictionary with the index as value t - e : i

nums_d = {}
for i, e in enumerate(nums):
if e in nums_d:
return [nums_d[e], i]
nums_d[target - e] = i

• Your first bullet point is only true if each number in the array is unique. Otherwise you override instead of append. Mar 23 '19 at 11:17
• @Graipher True, a defaultdict might be more appropriate there. Mar 23 '19 at 16:28
• $O(2n) = O(n).$ Mar 29 '19 at 0:23

You may assume that each input would have exactly one solution.

So there's no need to iterate over num twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.

With the input given, I'd try this:

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

def twoSum(nums, target):
for i in nums:
for m in nums[nums.index(i)+1:]:
if i + m == target:
return [nums.index(i), nums.index(m)]

print(twoSum(nums, target))

Say i + m is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m for which i + m = target, and return when found.

Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.

Also: thank you for mentioning Leetcode, it's new to me. Nice!

• Hey, long time no see! Unfortunately the code you've supplied is worse than the one in the question, as it takes $O(n^2)$ time and either $O(n)$ or $O(n^2)$ memory, depending on the GC. Where in the question it runs in $O(n)$ time and space. Yours is however easier to understand. Mar 22 '19 at 22:29
• Hi, yes, I know, Ludisposed pointed that out as well, hence the edit. I came across the question in Triage, and thought I might as well try an answer. Hadn't thought beyond nums given, with which it yields the answer in 1+3+1=5 iterations. I'm not familiar with O(n^2), but I guess that'd be 16 here? Mar 23 '19 at 18:54
• Ah, he must have deleted his comments. :( Yes it goes by the worst case, so if 11 and 15 were the targets. It's different from mathematics however, as your function runs in IIRC worst case $\frac{n^2}{2}$ iterations. And so it's mostly just a vague guess at performance. Mar 23 '19 at 22:19