数组中的 k-diff 数对 图解题解
这道题到底在问什么
- 输入
- nums=[3,1,4,1,5], k=2
- 输出
- 2（数对 (1,3)、(3,5)）
- 输入
- nums=[1,3,1,5,4], k=0
- 输出
- 1（只有 1 出现 ≥ 2 次）
先想最直接的笨办法
所有不同值都查完了，满足绝对差 2 的数对是 (1,3)、(3,5)，一共 2 对，和开头说的一致。回头看:靠一张频次表去重 + 对每个 x 查一次 x + k，没有两两暴力，一遍线性就数完了。（动画第 23 步）
最优解：一步一步想明白
- 3记住「频次表去重 → 对每个 x 查 x+k 在不在」，下面每帧都在套它。本例 k=2 走 k>0 主线。
- 4开局这排就是原数组，右边频次表还是空的。先逐个把元素记进频次表:同一个值再出现就把它的次数加一，这一步天然把重复值合并了。
- 5扫到下标 0 的 3，第一次见，记进频次表 count[3] = 1。
- 6扫到下标 1 的 1，第一次见，记进频次表 count[1] = 1。
- 7扫到下标 2 的 4，第一次见，记进频次表 count[4] = 1。
- 8又见到 1（下标 3），不新增一项，只把 count[1] 加到 2。重复值就这样被合并，后面只按「不同的值」来配对。
- 9扫到下标 4 的 5，第一次见，记进频次表 count[5] = 1。
- 10频次表建好，去重后只剩 4 个不同的值:1、3、4、5。k = 2 大于 0，接下来对每个不同的值 x，查 x + 2 在不在表里。
- 11轮到值 1（绿色标出它在数组里的位置）。要凑差 2，它的搭档应该是 1 + 2 = 3。下一步去频次表里查 3 在不在。
- 12拿着搭档 3 去频次表里翻:哈希查表是一步到位的 O(1) 操作，不用回头扫数组。看 3 这一项在不在表里。
- 13频次表里有 3!于是 1 和 3 配成一对 (1, 3)，答案加到 1。注意我们是按「不同的值」配的，所以哪怕 1 出现多次，这对也只算一次。
- 14轮到值 3（绿色标出它在数组里的位置）。要凑差 2，它的搭档应该是 3 + 2 = 5。下一步去频次表里查 5 在不在。
- 15拿着搭档 5 去频次表里翻:哈希查表是一步到位的 O(1) 操作，不用回头扫数组。看 5 这一项在不在表里。
- 16频次表里有 5!于是 3 和 5 配成一对 (3, 5)，答案加到 2。注意我们是按「不同的值」配的，所以哪怕 3 出现多次，这对也只算一次。
- 17轮到值 4（绿色标出它在数组里的位置）。要凑差 2，它的搭档应该是 4 + 2 = 6。下一步去频次表里查 6 在不在。
- 18拿着搭档 6 去频次表里翻:哈希查表是一步到位的 O(1) 操作，不用回头扫数组。看 6 这一项在不在表里。
- 19频次表里没有 6，4 找不到差 2 的搭档，跳过它，答案不变，还是 2。
- 20轮到值 5（绿色标出它在数组里的位置）。要凑差 2，它的搭档应该是 5 + 2 = 7。下一步去频次表里查 7 在不在。
- 21拿着搭档 7 去频次表里翻:哈希查表是一步到位的 O(1) 操作，不用回头扫数组。看 7 这一项在不在表里。
- 22频次表里没有 7，5 找不到差 2 的搭档，跳过它，答案不变，还是 2。
- 23所有不同值都查完了，满足绝对差 2 的数对是 (1,3)、(3,5)，一共 2 对，和开头说的一致。回头看:靠一张频次表去重 + 对每个 x 查一次 x + k，没有两两暴力，一遍线性就数完了。
⚠️ 容易写错的地方
✗ 错：按下标两两枚举、同一对值算多次
✓ 对：按「不同的值」配对,频次表天然去重
题目要的是不同数对,1 出现两次也只贡献一对 (1, 1+k)
✗ 错：k = 0 也套 x + k 查表
✓ 对：k = 0 单独处理:数「出现 ≥ 2 次」的值
k=0 时 x + k = x 永远在表里,会把每个值都误算成一对
✗ 错：只看 x − k 或只看 x + k 时重复计
✓ 对：统一只查 x + k 一个方向
每对 (x, x+k) 只在较小的 x 处被数到一次,不会重复
完整代码（Python / C++ / Java）
Python
from typing import List
from collections import Counter
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
count = Counter(nums)
if k == 0:
return sum(v > 1 for v in count.values())
vals = set(count)
return sum(1 for x in vals if x + k in vals)C++
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
unordered_map<int,int> count;
for (int x : nums) count[x]++;
int ans = 0;
if (k == 0) {
for (auto &p : count) if (p.second > 1) ans++;
} else {
for (auto &p : count) if (count.count(p.first + k)) ans++;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int findPairs(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
int ans = 0;
if (k == 0) {
for (int v : count.values()) if (v > 1) ans++;
} else {
for (int x : count.keySet()) if (count.containsKey(x + k)) ans++;
}
return ans;
}
}复杂度
时间
O(n)
建频次表扫一遍 O(n);再遍历不超过 n 个不同值、每个查一次表 O(1),合起来 O(n)
空间
O(n)
频次表最多存 n 个不同值
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组中的 k-diff 数对 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题和「两数之和」有什么联系和区别?+
都用哈希表把 O(n²) 枚举降到 O(n):两数之和是边扫边查「target − x」配某个具体和;本题是查「x + k」配固定的差。区别是本题要按数值去重、且 k=0 要特判,而两数之和返回的是下标、通常不去重。
k = 0 为什么要单独处理?+
差为 0 意味着两个数相等,这时 x + k 就是 x 自己、永远在表里,直接套主线会把每个值都误算成一对。正确做法是数「出现次数 ≥ 2」的值有几个,因为只有重复出现才凑得出 (x, x) 这一对。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组中的 k-diff 数对 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。