95. Gap of K Pairs
A museum records the ages (in years) of artefacts in the array nums. A curator wants to build display cases that each hold two artefacts whose ages differ by exactly k years, but the same pair of ages should never get two cases.
Return the number of distinct value pairs (a, b) with a <= b and b - a == k such that the array contains both an element equal to a and a different element (at another index) equal to b. Pairs are identified by their values, not by positions. When k is 0, a pair (a, a) counts when the value a occurs at least twice. The order of elements in nums does not matter.
Example 1
- Input:
- nums = [6,1,9,4,1,7], k = 3
- Output:
- 3
- Explanation:
The value pairs (1,4), (4,7) and (6,9) each differ by 3, so the answer is 3.
Example 2
- Input:
- nums = [2,2,2,5,5], k = 0
- Output:
- 2
- Explanation:
With k = 0 the values 2 and 5 each occur at least twice, giving 2.
Constraints
1 ≤ nums.length ≤ 5 * 105
-109 ≤ nums[i] ≤ 109
0 ≤ k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,800 msC++ 700 msJava 1,400 msJavaScript 1,400 msTypeScript 1,400 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)