Given an integer array nums
and an integer k
, return the number of pairs (i, j)
where i < j
such that |nums[i] - nums[j]| == k
.
The value of |x|
is defined as:
x
ifx >= 0
.-x
ifx < 0
.
Example 1:
Input: nums = [1,2,2,1], k = 1 Output: 4 Explanation: The pairs with an absolute difference of 1 are: - [1,2,2,1] - [1,2,2,1] - [1,2,2,1] - [1,2,2,1]
Example 2:
Input: nums = [1,3], k = 3 Output: 0 Explanation: There are no pairs with an absolute difference of 3.
Example 3:
Input: nums = [3,2,1,5,4], k = 2 Output: 3 Explanation: The pairs with an absolute difference of 2 are: - [3,2,1,5,4] - [3,2,1,5,4] - [3,2,1,5,4]
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99
Solution: Hashtable
|y – x| = k
y = x + k or y = x – k
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int countKDifference(vector<int>& nums, int k) { unordered_map<int, int> m; int ans = 0; for (int x : nums) { ans += m[x - k]; ans += m[x + k]; ++m[x]; } return ans; } }; |