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
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution