test two sum
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.
Each input has exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9, so we return [0, 1].
Example 2
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints
2 <= nums.length <= 104-109 <= nums[i], target <= 109- Exactly one valid answer exists.
Follow-up: can you do better than O(n2) time?
Brute force checks every pair in O(n²). Which part of that is repeated work?
For each number
x, you need to know quickly whether target - x has been seen before.A hash map from value to index answers "have I seen this?" in O(1).
Approach: one-pass hash map
Walk the array once. For each nums[i], check whether its complement target - nums[i] is already in the map. If it is, you have the answer. If not, store nums[i] → i and keep going.
class Solution:
def twoSum(self, nums, target):
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = iComplexity
- Time:
O(n), one pass with O(1) lookups. - Space:
O(n)for the map.
Interview tips
- Start by stating the O(n²) brute force, then improve it. Interviewers want to hear the trade-off.
- Ask: can the same value appear twice? (Yes, see
[3,3].) That is why you check before inserting.
Topics
Practice