题目
给你一个整数数组 nums
和一个整数 k
,请你返回数对 (i, j)
的数目,满足 i < j
且 |nums[i] - nums[j]| == k
。
|x|
的值定义为:
- 如果 x >= 0 ,那么值为 x 。
- 如果 x < 0 ,那么值为 -x 。
来源:力扣(LeetCode)
解答
通过哈希表来存储每一个数字出现的次数,然后依次遍历,由于是求绝对值,所以相差为k的数字,要么是当前数字减k,要么是加k,然后依次通过哈希表查找对应的数目,最终除以二即得最终结果。
class Solution {
public:
int countKDifference(vector<int>& nums, int k) {
unordered_map<int, int> mp;
int ret = 0;
for (auto i: nums) {
mp[i]++;
}
for (auto i: nums) {
ret += mp[i - k] + mp[i + k];
}
return ret/2;
}
};