I just submitted a Python solution to the 'Two Sum' problem on LeetCode.
The Problem
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[0] + nums[1] = 2 + 7 = 9
return
[0, 1]
.
My Solution
class Solution:
def twoSum(self, nums, target):
number_bonds = {}
for index, value in enumerate(nums):
if value in number_bonds:
return [number_bonds[value], index]
number_bonds[target - value] = index
return None
It was accepted and then told me the following:
Your runtime beats 83.12 % of python3 submissions.
This means that 16.88% of python3 submissions were more efficient than this one.
How can I get this more efficient than the solution provided above? Is there a funky way to do this with numpy that I'm not getting? Is there maybe another data structure I should use in this situation? Or a better algorithm altogether? I've explored a few alternate solutions and profiled with timeit
but none were faster than this.