LeetCode 题解工作台
差的绝对值为 K 的数对数目
给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i 且 |nums[i] - nums[j]| == k 。 |x| 的值定义为： 如果 x >= 0 ，那么值为 x 。 如果 x ，那么值为 -x 。 示例 1： 输入： nums = [1,2,2,1], …
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们注意到，数组 的长度不超过 ，因此我们可以枚举所有的数对 $(i, j)$，其中 $i < j$，并判断 $|nums[i] - nums[j]|$ 是否等于 ，是则答案加一。 最后返回答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一：暴力枚举
我们注意到，数组 的长度不超过 ，因此我们可以枚举所有的数对 ，其中 ，并判断 是否等于 ，是则答案加一。
最后返回答案即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
n = len(nums)
return sum(
abs(nums[i] - nums[j]) == k for i in range(n) for j in range(i + 1, n)
)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate efficiently uses a hash table for constant-time lookups.
- question_mark
Candidate demonstrates understanding of avoiding brute force pair checking.
- question_mark
Candidate handles edge cases like duplicates and missing pairs effectively.
常见陷阱
外企场景- error
Overcomplicating the problem with nested loops.
- error
Failing to manage hash table updates correctly, leading to double-counting.
- error
Not handling edge cases like empty arrays or arrays without valid pairs.
进阶变体
外企场景- arrow_right_alt
Consider using a set for tracking seen numbers instead of a hash table.
- arrow_right_alt
Adapt the solution for cases where negative values are allowed in the array.
- arrow_right_alt
Optimize further if the array is guaranteed to be sorted.