Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Exactly one valid pair exists, and you may not use the same element twice. Return the two indices in any order.
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
nums[0] + nums[1] = 2 + 7 = 9Example 2
Input: nums = [3,2,4], target = 6
Output: [1,2]
Constraints
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i], target <= 10^9
- Exactly one answer exists
Hints
Frequently asked at: Amazon, Google, Microsoft, Meta, Adobe, TCS, Infosys
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries every pair, which is O(n^2). For a number x, the only partner that works is target - x. If we remember every value we have already passed in a hash map, we can ask "have I seen the partner?" in O(1), so one pass is enough.
Algorithm
- Create an empty map from value to index.
- Walk through the array with index
iand valuex. - If
target - xis in the map, return[map[target - x], i]. - Otherwise store
x -> iand continue.
Time:
O(n)Space: O(n)Interview tip: Check the map before inserting the current number, otherwise
nums = [3,3], target = 6 can pair an element with itself.class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: seen = {} # value -> index for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return []Ctrl + Enter runs the examples