题目描述

给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

样例

输入: [3, 1, 4, 1, 5], k = 2
输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。

输入:[1, 2, 3, 4, 5], k = 1
输出: 4
解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。

输入: [1, 3, 1, 5, 4], k = 0
输出: 1
解释: 数组中只有一个 0-diff 数对，(1, 1)。

注意

• 数对 (i, j) 和数对 (j, i) 被算作同一数对。
• 数组的长度不超过10,000。
• 所有输入的整数的范围在 [-1e7, 1e7]。

算法1

(排序，扫描) $O(n \log n)$

1. 将原数组从小到大排序。
2. 定义 i 和 j 依次扫描可能的答案数对；对于每一个不同的 nums[i]，尝试找到对应的 nums[j] (j >= i)，使得 nums[j] - nums[i] == k。若找到了 nums[j]，则答案加一。
3. 这里的 j 是单调递增的，所以每个数字最多只会被遍历两次。

时间复杂度

• 排序后，每个数字最多只会被遍历两次，故时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        sort(nums.begin(), nums.end());
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (i > 0 && i < n && nums[i] == nums[i - 1])
                i++;
            if (i >= n)
                break;
            while (j < n && (j <= i || nums[j] - nums[i] < k))
                j++;

            if (j < n && nums[j] - nums[i] == k)
                ans++;
        }
        return ans;
    }
};

算法2

(哈希表) $O(n)$

1. 定义两个哈希表 unordered_set，hash 存储数字，first_ele 存储答案数对中较小的数字。
2. 从头开始遍历数组，对于 nums[i], 若在 hash 中发现 nums[i] - k，则将 nums[i] - k 存入 first_ele 中；若在 hash 中发现 nums[i] + k，则将 nums[i] 存入 first_ele 中。然后 nums[i] 存入 hash 中。
3. 最后，答案就是 first_ele 的大小。
4. 注意，需要特判 k < 0，直接输出 0。

时间复杂度

• 哈希表的单次操作时间复杂度为 $O(1)$，故总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0)
            return 0;

        unordered_set<int> hash, first_ele;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.find(nums[i] - k) != hash.end()) first_ele.insert(nums[i] - k);
            if (hash.find(nums[i] + k) != hash.end()) first_ele.insert(nums[i]);
            hash.insert(nums[i]);
        }
        return first_ele.size();
    }
};