0532. K-diff Pairs in an Array
==============================
题目信息
--------
:题号: 0532
:难度: Medium
:主题: 数组、绝对差、不同数值对、重复元素
:原题: `LeetCode 0532 `_
:重点: 统计满足绝对差为 k 的不同数值对、同一对不能因下标组合重复计数、k=0 时要求值至少出现两次
题目重述
--------
给定整数数组 ``nums`` 和非负整数 ``k``,统计有多少个不同的数值对 ``(a, b)`` 满足 ``|a - b| = k``,且 ``a``、``b`` 都来自数组中的不同位置。
答案按数值对去重,而不是按下标对计数;同一组数值即使由多组下标形成,也只计一次。当 ``k = 0`` 时,只有在某个值至少出现两次时,数值对 ``(x, x)`` 才成立。
自建示例
--------
重复值不重复贡献同一数值对:
.. code-block:: text
输入:nums = [1,3,1,5,4],k = 2
输出:2
解释:不同数值对为 (1,3) 和 (3,5);两个数值 1 不会让 (1,3) 被重复计数。
零差值:
.. code-block:: text
输入:nums = [2,2,2,3],k = 0
输出:1
解释:只有数值 2 至少出现两次,因此唯一数值对是 (2,2)。
先压缩出现次数再按数值查找
--------------------------
频次表把下标差异压缩为数值集合。若 ``k > 0``,每个出现过的 ``x`` 至多贡献一次数值对 ``(x, x+k)``;若 ``k = 0``,只有频次至少为 2 的 ``x`` 能贡献 ``(x,x)``。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int findPairs(std::vector& nums, int k) {
std::unordered_map 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)``。