Count Pairs with Sum
Medium · rating 1400 · Arrays, Hashing
The first line contains n and a target. The second line contains n integers. Print the number of index pairs (i, j) with i < j and a[i] + a[j] = target.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
A single pass with a hash map of value counts. For each element x, the number of valid partners already seen is the count of target − x; add that, then record x. Counting the complement before inserting x avoids pairing an element with itself and naturally handles duplicates.
from collections import Counter
seen, count = Counter(), 0
for x in a:
count += seen[target - x]
seen[x] += 1
print(count)Complexity
Time: O(n). Space: O(n).
Related problems
- Count Pairs With Difference — Medium
- Most Common Value — Medium
- Two Sum Exists — Medium
- Most Frequent Element — Medium
- Subarrays Summing to K — Hard
- Two Sum — Easy