244. Pairs That Add Up
Core1000 ms256 MBSolved by 0%
Given n integers and a target t, print how many pairs of positions
(i, j) with i < j satisfy a[i] + a[j] == t.
Pairs of positions, not of values. In 2 2 2 2 with a target of 4, every one
of the six pairs of positions counts.
The obvious solution checks every pair, which is n(n-1)/2 comparisons. At
n = 200000 that is about twenty billion, and the largest test is sized so
that it will not finish. Sort first and the same question can be answered with
two pointers walking towards each other.
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 in any order.
Output
Print one integer, the number of index pairs summing to t.
Input4 5
1 2 3 4
Output2
Noteis 1+4 and 2+3
Input3 7
1 2 3
Output0
Notehas no pair reaching the target
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.