Count Pairs with Sum

Efficiently count unordered pairs that add up to a target using a hash map.

dictionary pair-counting hash-map

Write a function `count_pairs(nums, target)` that takes a list of integers `nums` and an integer `target`. The function should return the number of unordered pairs (i, j) with i < j such that `nums[i] + nums[j] == target`. Each pair is identified by the values, not indices; if the same value appears multiple times, each combination counts separately. For example, `[1, 1, 1]` with target 2 has 3 pairs using indices (0,1), (0,2), (1,2).

Implement the function in Python. The input list may be empty; then the result is 0. Values can be negative. The expected time complexity is O(n).

Constraints

0 <= len(nums) <= 100000
-10^9 <= nums[i], target <= 10^9

Example

>>> count_pairs([1, 2, 3, 4], 5)
2
>>> count_pairs([1, 1, 1], 2)
3
>>> count_pairs([], 0)
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about using a dictionary to store how many times you've seen a number so far.

For each number, check if (target - num) has been seen before; add its count to the total.

Update the dictionary after processing each number to avoid double counting.

The count of pairs when numbers repeat is the product of their frequencies; handle by counting on the fly.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.