哈希表题目：数组中的 k-diff 数对

题目

标题和出处

标题：数组中的 k-diff 数对

出处：532. 数组中的 k-diff 数对

难度

4 级

题目描述

要求

给定一个整数数组 $\text{nums}$ 和一个整数 $\text{k}$，返回不同的 $\text{k}$-diff 数对的数目。

一个 $\text{k}$-diff 数对为一个整数对 $\text{(nums[i], nums[j])}$，并满足下述条件：

• $\text{0}\le \text{i, j}<\text{nums.length}$
• $\text{nums[i]}\le \text{nums[j]}$
• $\text{|nums[i] - nums[j]|}=\text{k}$

注意，$\text{|val|}$ 表示 $\text{val}$ 的绝对值。

示例

示例 1：

输入：$\text{nums = [3, 1, 4, 1, 5], k = 2}$
输出：$\text{2}$
解释：数组中有两个 $\text{2}$-diff 数对，$\text{(1, 3)}$ 和 $\text{(3, 5)}$。
尽管数组中有两个 $\text{1}$，但我们只应返回不同的数对的数量。

示例 2：

输入：$\text{nums = [1, 2, 3, 4, 5], k = 1}$
输出：$\text{4}$
解释：数组中有四个 $\text{1}$-diff 数对，$\text{(1, 2)}$，$\text{(2, 3)}$，$\text{(3, 4)}$ 和 $\text{(4, 5)}$。

示例 3：

输入：$\text{nums = [1, 3, 1, 5, 4], k = 0}$
输出：$\text{1}$
解释：数组中只有一个 $\text{0}$-diff 数对，$\text{(1, 1)}$。

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{4}}$
• ${\text{-10}}^{\text{7}}\le \text{nums[i]}\le {\text{10}}^{\text{7}}$
• $\text{0}\le \text{k}\le {\text{10}}^{\text{7}}$

解法

思路和算法

由于题目要求计算数组 $\text{nums}$ 中的不同的差为 $k$ 的数对的数目，因此只需要考虑数组中有哪些数字，不需要考虑顺序。

计算差为 $k$ 的数对的数目需要考虑两种情况，分别是 $k=0$ 和 $k>0$。

当 $k=0$ 时，每个差为 $k$ 的数对由两个相等的整数组成，对于任意整数 $\text{num}$，只有当 $\text{num}$ 在数组 $\text{nums}$ 中出现次数大于 $1$ 次时，才有数对 $(\text{num},\text{num})$。遍历数组 $\text{nums}$ 并用哈希表记录每个数字的出现次数，然后遍历哈希表，对于哈希表中的每个数字，如果出现次数大于 $1$ 次，则将数对的数目加 $1$。遍历哈希表结束之后即可得到差为 $k$ 的数对的数目。

当 $k>0$ 时，每个差为 $k$ 的数对由两个不相等的整数组成，对于任意整数 $\text{num}$，当 $\text{num}$ 和 $\text{num}+k$ 都在数组中出现时，有数对 $(\text{num},\text{num}+k)$。遍历数组 $\text{nums}$ 并用哈希集合记录出现的数字，然后遍历哈希集合，对于哈希集合中的每个数字 $\text{num}$，如果 $\text{num}+k$ 也在哈希集合中，则将数对的数目加 $1$。遍历哈希集合结束之后即可得到差为 $k$ 的数对的数目。

代码

class Solution {public int findPairs(int[] nums, int k) {int pairs = 0;if (k == 0) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}Set<Integer> set = map.keySet();for (int num : set) {if (map.get(num) > 1) {pairs++;}}} else {Set<Integer> set = new HashSet<Integer>();for (int num : nums) {set.add(num);}for (int num : set) {if (set.contains(num + k)) {pairs++;}}}return pairs;}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要遍历数组一次，使用哈希表或哈希集合存储数组中的不同数字，然后遍历哈希表或哈希集合一次，由于哈希表或哈希集合中的元素个数不超过数组长度，因此时间复杂度是 $O(n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要使用哈希表或哈希集合存储数组中的不同数字，最坏情况下需要存储数组中的全部数字。