LeetCode 523. 数组中的 k-diff 数对

给定一个整数数组和一个整数 k，你需要在数组里找到 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j])，并满足下述全部条件：

• 0 <= i < j < nums.length
• |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)。

方法一：哈希表
思路
遍历数组，找出符合条件的数对。因为是寻找不同的数对，所以可以将数对放入哈希表 res，完成去重的效果，最后返回哈希表的长度即可。遍历数组时，可以将遍历到的下标当作潜在的 j，判断 j左侧是否有满足条件的 i 来构成 k-diff 数对，而这一判断也可以通过提前将下标 j左侧的元素都放入另一个哈希表 visited 来降低时间复杂度。如果可以构成，则将数对放入哈希表 res。
代码实现时，由于 k 是定值，知道数对的较小值，也就知道了另一个值，因此我们可以只将数对的较小值放入res，而不影响结果的正确性。判断完之后，再将当前元素放入visited，作为后续判断潜在的 nums[i]。

public class Solution {
    public int FindPairs(int[] nums, int k) 
    {
        ISet visited = new HashSet();
        ISet res = new HashSet();
        foreach (int num in nums) 
        {
            if (visited.Contains(num - k)) 
            {
                res.Add(num - k);
            }
            if (visited.Contains(num + k)) 
            {
                res.Add(num);
            }
            visited.Add(num);
        }
        return res.Count;
    }
}