Two Sum easy
Description
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Examples
> Case 1:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9
> Case 2:
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
> Case 3:
Input: nums = [3, 3], target = 6
Output: [0, 1]Constraints
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- Only one valid answer exists.
Approach 1: Brute Force
Check every pair of elements. Simple but slow.
Approach 2: Hash Map (Optimal)
The key insight: for each number x, we need to find if target - x already exists. A hash map gives us O(1) lookups.
Hash Map approach: nums=[2, 7, 11, 15], target=9
Step 1 of 2
2
[0]7
[1]11
[2]15
[3]i=0, num=2. Need 9-2=7. Map is empty, so 7 not found. Store {2: 0}.
Explanation
- We iterate through the array once
- For each element, we calculate what its “complement” would be:
target - nums[i] - We check if we’ve already seen this complement in our hash map
- If yes, we found our pair and return both indices
- If no, we store the current element and its index in the map for future lookups
- The hash map trades O(n) space for O(1) lookups, turning an O(n^2) problem into O(n)
Why this is problem #1 on LeetCode: Two Sum teaches the fundamental pattern of using a hash map to convert “find a pair” problems from O(n^2) to O(n). This same pattern appears in dozens of other problems.
Analysis
- Time Complexity:
O(n)— single pass through the array - Space Complexity:
O(n)— hash map stores at most n elements