LeetCode 题解工作台
数组中的 k-diff 数对
给你一个整数数组 nums 和一个整数 k ，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。 k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件： 0 i != j |nums[i] - nums[j]| == k…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
由于 是一个定值，我们可以用一个哈希表 记录数对的较小值，就能够确定较大的值。最后返回 的大小作为答案。 遍历数组 ，当前遍历到的数 ，我们用哈希表 记录此前遍历到的所有数字。若 在 中，则将 添加至 ；若 在 中，则将 添加至 。然后我们将 添加至 。继续遍历数组 直至遍历结束。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：
0 <= i, j < nums.lengthi != j|nums[i] - nums[j]| == k
注意，|val| 表示 val 的绝对值。
示例 1：
输入：nums = [3, 1, 4, 1, 5], k = 2 输出：2 解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。 尽管数组中有两个 1 ，但我们只应返回不同的数对的数量。
示例 2：
输入：nums = [1, 2, 3, 4, 5], k = 1 输出：4 解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5) 。
示例 3：
输入：nums = [1, 3, 1, 5, 4], k = 0 输出：1 解释：数组中只有一个 0-diff 数对，(1, 1) 。
提示：
1 <= nums.length <= 104-107 <= nums[i] <= 1070 <= k <= 107
解题思路
方法一：哈希表
由于 是一个定值，我们可以用一个哈希表 记录数对的较小值，就能够确定较大的值。最后返回 的大小作为答案。
遍历数组 ，当前遍历到的数 ，我们用哈希表 记录此前遍历到的所有数字。若 在 中，则将 添加至 ；若 在 中，则将 添加至 。然后我们将 添加至 。继续遍历数组 直至遍历结束。
最后返回 的大小作为答案。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
ans = set()
vis = set()
for x in nums:
if x - k in vis:
ans.add(x - k)
if x + k in vis:
ans.add(x)
vis.add(x)
return len(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They mention unique pairs, which signals that duplicate values must be collapsed instead of counted by index.
- question_mark
They highlight k = 0, which is a cue to switch from difference lookup to frequency-at-least-two logic.
- question_mark
They ask about Array, Hash Table, and Two Pointers together, which usually means they want you to compare the hash-count method with the sorted duplicate-safe sweep.
常见陷阱
外企场景- error
Counting index pairs instead of unique value pairs, especially when the array contains repeated numbers.
- error
Using the same rule for k = 0 and k > 0, which misses that zero-diff pairs require duplicates of the same value.
- error
Forgetting to skip duplicates in the sorted two-pointer approach, causing the same pair to be counted multiple times.
进阶变体
外企场景- arrow_right_alt
Return the actual unique k-diff pairs instead of just the count, which means storing the value pairs you confirm.
- arrow_right_alt
Handle many queries with different k values on the same nums array, which changes whether preprocessing frequencies or sorting is more useful.
- arrow_right_alt
Count pairs with difference at most k instead of exactly k, which turns the sorted two-pointer logic into a window-style counting problem.