2006. 差的绝对值为 K 的数对数目

🟢   🔖  数组 哈希表 计数  🔗 力扣 LeetCode

题目

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 if x >= 0.
• -x if x < 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

题目大意

给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。

|x| 的值定义为：

• 如果 x >= 0 ，那么值为 x 。
• 如果 x < 0 ，那么值为 -x 。

示例 1：

输入： nums = [1,2,2,1], k = 1

输出： 4

解释： 差的绝对值为 1 的数对为：

• [1 ,2 ,2,1]
• [1 ,2,2 ,1]
• [1,2 ,2,1]
• [1,2,2 ,1]

示例 2：

输入： nums = [1,3], k = 3

输出： 0

解释： 没有任何数对差的绝对值为 3 。

示例 3：

输入： nums = [3,2,1,5,4], k = 2

输出： 3

解释： 差的绝对值为 2 的数对为：

• [3 ,2,1 ,5,4]
• [3 ,2,1,5 ,4]
• [3,2 ,1,5,4]

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100
• 1 <= k <= 99

解题思路

使用哈希表记录当前元素出现的次数，从而高效统计符合条件的元素对，避免暴力双循环的时间复杂度 O(n^2)。

• 使用一个 Map 记录数组中每个数字的出现频率，动态更新频率表。
• 遍历数组时，对于每个元素 num：
  • 检查 num - k 是否存在于频率表中，若存在，则将对应频率加到结果中。
  • 检查 num + k 是否存在于频率表中，若存在，则将对应频率加到结果中。
• 更新 num 在频率表中的值，表示当前遍历到的数字出现了一次。
• 返回累计的计数结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组的长度，遍历数组一次。
• 空间复杂度：O(n)，频率表存储数组中每个元素的频率，最坏情况下存储 n 个元素。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countKDifference = function (nums, k) {
	let freq = new Map(); // 用于存储每个数字的频率
	let count = 0;

	for (let num of nums) {
		// 检查差值为 k 的数字是否已经出现
		if (freq.has(num - k)) {
			count += freq.get(num - k);
		}
		if (freq.has(num + k)) {
			count += freq.get(num + k);
		}
		// 更新当前数字的频率
		freq.set(num, (freq.get(num) || 0) + 1);
	}

	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
1	两数之和	[✓]	数组 哈希表	🟢	🀄️ 🔗
532	数组中的 k-diff 数对		数组 哈希表 双指针 2+	🟠	🀄️ 🔗
1865	找出和为指定值的下标对		设计 数组 哈希表	🟠	🀄️ 🔗
2176	统计数组中相等且可以被整除的数对	[✓]	数组	🟢	🀄️ 🔗
2364	统计坏数对的数目		数组 哈希表 数学 1+	🟠	🀄️ 🔗
2563	统计公平数对的数目	[✓]	数组 双指针 二分查找 1+	🟠	🀄️ 🔗