0532. K-diff Pairs in an Array¶
题目信息¶
- 题号:
0532
- 难度:
Medium
- 主题:
数组、绝对差、不同数值对、重复元素
- 原题:
- 重点:
统计满足绝对差为 k 的不同数值对、同一对不能因下标组合重复计数、k=0 时要求值至少出现两次
题目重述¶
给定整数数组 nums 和非负整数 k,统计有多少个不同的数值对 (a, b) 满足 |a - b| = k,且 a、b 都来自数组中的不同位置。
答案按数值对去重,而不是按下标对计数;同一组数值即使由多组下标形成,也只计一次。当 k = 0 时,只有在某个值至少出现两次时,数值对 (x, x) 才成立。
自建示例¶
重复值不重复贡献同一数值对:
输入:nums = [1,3,1,5,4],k = 2
输出:2
解释:不同数值对为 (1,3) 和 (3,5);两个数值 1 不会让 (1,3) 被重复计数。
零差值:
输入:nums = [2,2,2,3],k = 0
输出:1
解释:只有数值 2 至少出现两次,因此唯一数值对是 (2,2)。
先压缩出现次数再按数值查找¶
频次表把下标差异压缩为数值集合。若 k > 0,每个出现过的 x 至多贡献一次数值对 (x, x+k);若 k = 0,只有频次至少为 2 的 x 能贡献 (x,x)。
C++ 实现¶
class Solution {
public:
int findPairs(std::vector<int>& nums, int k) {
std::unordered_map<int, int> frequency;
for (int value : nums) ++frequency[value];
int answer = 0;
for (const auto& [value, count] : frequency) {
if (k == 0) {
if (count >= 2) ++answer;
} else if (frequency.count(value + k) != 0) {
++answer;
}
}
return answer;
}
};
代码分析¶
遍历频次表而非原数组,保证同一数值对不会按多个下标重复计数;k=0 单独检查重复出现条件。平均时间复杂度为 O(n),额外空间复杂度为 O(n)。