LeetCode 532. 数组中的 k-diff 数对
题目描述
给定整数数组和k≥0，统计数值之差的绝对值为k的不同数值对。相同数值对只计一次；k=0时需要同一个值至少出现两次。
示例 1：
输入：nums = [3,1,4,6,5], k = 3
输出：2
解释：不同数值对为 (1,4)、(3,6)，每对只计一次。
提示：
- k≥0；按数值对去重，不按下标对计数。k=0 时必须选择两个不同位置上相同的值。
题意分析
统计数组中数值之差的绝对值等于
k的不同数值对。两个元素必须来自不同位置，但答案按数值对去重：同一组数值即使有许多下标组合，也只计一次。题目中
k非负。k > 0时两个数值不同；k = 0时两端数值相同，但仍然需要数组中存在至少两次出现，不能让一个元素与自己配对。
解法：按不同数值查找差值伙伴
核心思路
[!blue]
先统计每个数值的频次，随后只遍历不同的数值键，而不是遍历所有原下标。这样同一个值出现多次，不会让相同数值对被反复统计，同时频次信息仍足以判断能否选出两个真实位置。
当
k > 0，把每一对统一表示为较小端x和较大端x + k。对每个不同的x，只查找x + k是否存在：存在就计一对，不再检查反方向的x - k，也不乘两端的出现次数。任意合法数值对都有唯一的较小端，所以一定会在枚举这个端点时被找到；另一个端点向更大方向查询，不会反过来把同一对再算一次。频次表按键去重与只向一个方向查询，分别消除了重复出现和方向对称带来的重复。
当
k = 0，查找x + k只会找到自己，无法保证用了两个不同位置。此时应改为检查count[x] >= 2，满足就贡献唯一的数值对(x, x)；即使这个值出现更多次，仍只增加一。全部不同值处理完成，累计数量就是答案。负数同样能按大小关系查询伙伴，不需要排序，也不需要修改输入。
解题步骤
- 统计每个数值的出现次数。
- 遍历所有不同值，若
k > 0，只检查它的较大伙伴x + k是否存在。- 若
k = 0，改为检查当前值是否至少出现两次。- 每个满足条件的键只增加一对，最后返回累计数。
代码实现
class Solution {
public int findPairs(int[] nums, int k) {
if (k < 0) {
return 0;
}
Map<Long, Integer> count = new HashMap<>();
for (int x : nums) {
count.merge((long) x, 1, Integer::sum);
}
int answer = 0;
for (long x : count.keySet()) {
if (k == 0 ? count.get(x) > 1 : count.containsKey(x + k)) {
answer++;
}
}
return answer;
}
}
func findPairs(nums []int, k int) int {
if k < 0 {
return 0
}
count := map[int]int{}
for _, x := range nums {
count[x]++
}
answer := 0
for x, c := range count {
if k == 0 {
if c > 1 {
answer++
}
} else if count[x+k] > 0 {
answer++
}
}
return answer
}
复杂度分析
- 时间复杂度：平均 $O(n)$。建表扫描
n个元素，之后对d个不同值各做一次查询，且d <= n。- 空间复杂度：$O(d)$，保存不同值及其频次，最坏为 $O(n)$。
关键点总结
[!green]
- 统计对象是不同数值对，次数只用于判断位置是否足够，不用于计算下标组合数。
- 正差值只从较小端查较大端，避免方向重复。
- 零差值需要至少两次真实出现，单纯存在性不能满足条件。
易错点总结
[!yellow]
- 对每个原数组位置累加答案，会重复计算由重复值形成的同一数值对。
- 同时检查
x + k和x - k，会把正差值数对的两个方向都算入。- 把两端频次相乘，得到的是下标配对数量，不是题目要求的不同数值对数量。
k = 0时只检查该值存在，会错误允许同一位置与自己配对。- 先用集合完全丢弃次数，会失去判断零差值需要的重复信息。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 都对一个值查询互补值；本题查 x+k 并按数值对去重，原题查 target-x 并返回下标。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！