Description
Return the indices of two distinct array entries whose sum is target. Exactly one pair exists.
Solution
def two_sum(nums, target):
positions = {}
for i, value in enumerate(nums):
if target - value in positions:
return [positions[target - value], i]
positions[value] = iExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[4,8,3],11]- Output
[1,2]
The values 8 and 3 at indices 1 and 2 sum to 11.
Example 2
- Input
[[3,3],6]- Output
[0,1]
Two distinct positions both contain 3.
Example 3
- Input
[[-2,5,9],7]- Output
[0,2]
The values -2 and 9 sum to 7.
Approach
Before storing the current value, look up the complement among earlier positions.
Time & space
O(n) expected time; O(n) space, for n entries.