Easy
Two Sum
- Time limit
- 1 s
- Memory limit
- 256 MB
- Estimated
- 20 min
Description
Description
Given an integer array nums and an integer target, find two indices i and j (with i < j) such that nums[i] + nums[j] == target.
At least one such pair is guaranteed to exist. If more than one pair satisfies the condition, resolve the tie deterministically: scan the array from left to right while keeping a map from each value seen so far to its most recently seen index. The first time you reach an index j whose complement (target - nums[j]) is already in the map, return [i, j] where i is the map's current entry for that complement.
Examples
Example 1
- Input:
nums = [2, 7, 11, 15], target = 9 - Output:
[0, 1] - Explanation:
nums[0] + nums[1] = 2 + 7 = 9.
Example 2
- Input:
nums = [3, 2, 4], target = 6 - Output:
[1, 2]
Constraints
2 <= nums.length <= 100000-1000000000 <= nums[i] <= 1000000000-1000000000 <= target <= 1000000000- At least one valid pair
(i, j)withi < jandnums[i] + nums[j] == targetexists. - When several valid pairs exist, the tie-break rule in the description determines the unique expected answer.
Sample cases
3Sample 1
Input
nums = [2,7,11,15] target = 9
Expected output
[0,1]
Sample 2
Input
nums = [3,2,4] target = 6
Expected output
[1,2]
Skills and languages
Patterns
- Complement Lookup
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer