300. Count Pairs With a Given Sum
Given n integers and a target t, print how many pairs of positions
(i, j) with i < j have a[i] + a[j] == t.
Problem 244 solved this by sorting and using two pointers. This one asks for the
map version, which is O(n) rather than O(n log n).
Count how many times each value occurs. For each distinct value v, its
partner is t - v. When they differ, every copy of one pairs with every copy
of the other. When v is its own partner, the count is c choose 2 instead.
Counting each unordered pair exactly once is the whole difficulty.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - `-2000000000 ≤ t ≤ 2000000000`
Input
The first line contains two integers n and t.
The second line contains n integers.
Output
Print one integer, the number of index pairs summing to t.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.