Count Pairs With a Given Sum
- Time limit
- 1.5 s
- Memory limit
- 128 MB
- Estimated
- 25 min
- Hash-Based Techniques
Description
Given an integer array nums and an integer target, return the number of index pairs (i, j) such that i < j and nums[i] + nums[j] == target.
Each pair is identified by its two indices, not just by its values. Therefore, duplicate values at different positions contribute separate pairs. You must count every valid pair exactly once.
An approach that checks every possible pair takes quadratic time. Design a more efficient solution using the values seen so far so that each new element can be matched against the number of previously seen complements.
Example 1: nums = [1, 2, 3, 4], target = 5 returns 2, corresponding to index pairs (0, 3) and (1, 2).
Example 2: nums = [1, 1, 1, 1], target = 2 returns 6, because every pair of distinct indices is valid.
Example 3: nums = [-1, 0, 1, 2, -1, -4], target = 0 returns 2.
Constraints
- 0 <= nums.length <= 100
- -10^9 <= nums[i] <= 10^9
- -2 * 10^9 <= target <= 2 * 10^9
- The answer may exceed the 32-bit signed integer range; return a long.
- Expected time complexity: O(n) average time using a hash map; expected auxiliary space: O(n).
Sample cases
3Sample 1
Input
nums = [1,2,3,4] target = 5
Expected output
2
Sample 2
Input
nums = [1,1,1,1] target = 2
Expected output
6
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