Checking every pair of elements costs O(n^2). A hash map lets you ask "have I already seen the number I need?" in O(1), so a single pass is enough.
Given a list of integers nums and an integer target, return the indices of the two numbers that add up to target, as a list of two integers. Each input has exactly one answer, and you may not use the same element twice. The two indices may be returned in either order.
Examples
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] == 9
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: [0, 0] is not allowed because it uses the same element twice.
Constraints
2 <= len(nums) <= 10**4-10**9 <= nums[i], target <= 10**9
Goals
- Use a dictionary to remember values you have already seen along with their positions
- Rephrase 'find a pair' as 'for each element, look up its partner'