269. Pairs a Fixed Distance Apart
Core1000 ms256 MBSolved by 0%
Given n integers and a value k, print how many pairs of positions
(i, j) with i < j satisfy |a[i] - a[j]| == k.
Watch k = 0. Then the pair must be two positions holding the SAME value, and
three equal values give three pairs rather than one.
Checking every pair is quadratic. Sort first, and for each value you can look for its partner instead of scanning: either with two pointers moving in the same direction, or with a binary search per element.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 1000000000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the number of index pairs whose values differ by exactly k.
Input5 1
1 5 3 4 2
Output4
Notehas four consecutive pairs once sorted
Input3 0
1 2 3
Output0
Notehas k of zero with no repeated values
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.