难度: Easy
给你一个整数数组 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 <= 2001 <= nums[i] <= 1001 <= k <= 99运行时间: 30 ms
内存: 16.1 MB
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
dic={}
for item in nums:
if item not in dic:
dic[item]=1
else:
dic[item]+=1
ans=0
for item in dic:
if item-k in dic:
ans+= dic[item]*dic[item-k]
return ans
这个题解采用了哈希表的方法。首先，遍历数组nums，用一个字典dic来记录每个元素出现的次数。然后，再次遍历字典中的每个元素，检查其与k之差是否也在字典中。如果是，那么这两个数就可以形成满足条件的数对。由于我们是在字典中查找，因此可以保证数对中的第一个数小于第二个数，从而避免了重复计算。最后，将所有满足条件的数对数量累加起来，就得到了最终的答案。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
dic = {} # 创建一个空字典用于存储每个元素出现的次数
for item in nums:
if item not in dic:
dic[item] = 1
else:
dic[item] += 1
ans = 0
for item in dic:
if item - k in dic:
ans += dic[item] * dic[item - k] # 累加满足条件的数对数量
return ans
哈希表（或字典）在这种场景下使用主要是因为它提供了非常快速的查找、插入和更新操作的平均时间复杂度，通常是O(1)。对于本题目，需要频繁地检查元素是否存在于集合中并更新元素的计数，哈希表可以非常高效地支持这些操作。而使用数组虽然也可以实现，但当元素范围很大或非连续时，会造成空间的浪费或无法实现。链表则因为查找和更新操作需要O(n)的时间复杂度而不适合。
在算法中，通过确保只计算`item - k`（其中`item`是字典的键）的情况，而不是同时计算`item + k`和`item - k`，可以避免重复。具体来说，当我们考虑每个元素`item`时，只检查`item - k`是否存在于字典中，这样就只统计每个满足条件的数对一次，因为对于每个数对（a, b），我们只在处理`b`时计算`b - a = k`，而不会在处理`a`时重复计算`a - b = k`。
代码中确实只考虑了`item - k`的情况，并没有直接考虑`item + k`。这是因为选取任一方向（`item - k`或`item + k`）就足以覆盖所有可能的数对，而且可以避免重复计算。如果同时考虑`item + k`，则需要额外的逻辑来确保不重复计算同一对数。因此，选择任一方向检查就可以有效地实现需求，并简化代码逻辑。
当`k`为0时，题目要求找出相同数值的数对。在这种情况下，算法在统计时需要略作调整，即对于每个元素`item`，计算其在字典中的出现次数`dic[item]`，然后使用组合数公式计算可以形成的数对数目：`dic[item] * (dic[item] - 1) / 2`。这是因为每对相同的元素都可以形成一个数对，而每个元素可以与之前的相同元素组成数对。