two sum python solution
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in nums:
j=target-i
if ((j in nums)==True and (nums.index(j) != nums.index(i))):
return [nums.index(i), nums.index(j)]
it passed the case for list [2,7,11,15] but not [3,3]. I am not sure what the issue is.
This works and can do it in a single pass:
from collections import defaultdict
# Returns the indices of two numbers that add up to the target
def two_sums(nums, target):
lookup = defaultdict(list)
for i, num in enumerate(nums):
needed = target - num
if needed in lookup:
return [lookup[needed][0], i]
lookup[num].append(i)
return None
print(two_sums([2,7,11,15], 17))
print(two_sums([3, 3], 6))
Another solution might be:
def two_sum(nums, target):
d = {}
for i in range(len(nums)):
x = nums[i]
if target - x in dict:
return (d[target - x] + 1, i + 1)
d[x] = i
return None
I found 3 main ways to solve this question, the 1st approach is brute force with time complexity of O(n^2) and space complexity of O(1):
def twoNumberSum(array, targetSum):
for i in range(0, len(array)):
for j in range(i+1, len(array)):
if array[i] + array[j] == targetSum:
return ([array[i], array[j]])
return []
The 2nd approach is using hash map with time complexity of O(n) and space complexity of O(n):
def twoNumberSum(array, targetSum):
matches = {}
for number in array:
match = targetSum - number
if match in matches:
return [match, number]
else:
matches[number] = True
return []
The 3rd approach is with two pointers of left and right. This method has time complexity of O(nlogn) and space complexity of O(1):
def twoNumberSum(array, targetSum):
array.sort()
left = 0
right = len(array) - 1
while left < right:
if array[left] + array[right] == targetSum:
return [array[left], array[right]]
elif array[left] + array[right] < targetSum:
left +=1
elif array[left] + array[right] > targetSum:
right -=1
return []