LeetCode532. 数组中的 k-diff 数对

题目描述

本题目来自LeetCode上的『532. 数组中的 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，但我们只应返回不同的数对的数量。

提示

1 <= nums.length <= 10^4
-10^7 <= nums[i] <= 10^7
0 <= k <= 10^7

题解1 - 哈希表

本题有一点 两数之和 进阶题的感觉。对于每一组数对 $(i,j)$，我们只需要找出较小值的数量即可，使用哈希表 mp 保存已经遍历过的数，再使用一个哈希集合 ans 实现去重功能，对于当前的数 $num$：

查找 $num - k$ 是否已经遍历过，如果能找到，则将 $num-k$ 加入到 ans 中。
查找 $num + k$ 是否已经遍历过，如果能找到，则将 $num$ 加入到 ans 中。

最后返回 ans 的大小即可。

代码

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_set<int> mp;
        unordered_set<int> ans;
        for (const auto& num: nums) {
            if (mp.find(num - k) != mp.end()) {
                ans.emplace(num - k);
            }
            if (mp.find(num + k) != mp.end()) {
                ans.emplace(num);
            }
            mp.emplace(num);
        }
        return ans.size();
    }
};

复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(n)$

题解2 - 排序+二分查找

对于某个数对 $(i,j)$，可以枚举其中较小的数，然后查找另一个数即可。为了方便查找，需要先对数组进行排序，然后进行二分查找，设当前数为 $nums[i]$，则查找目标为 $nums[i]+k$，查找范围为 $[i+1,n)$。

为了保证不重复计数，要跳过相同的数，利用数组的有序性，使用 i && nums[i - 1] == nums[i] 就可以判断。

代码

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        int ans = 0, n = nums.size();
        sort(nums.begin(), nums.end());

        auto binarySearch = [&](int i, int x) -> int {
            int left = i + 1, right = n - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] < x) {
                    left = mid + 1;
                } else if (nums[mid] > x) {
                    right = mid - 1;
                } else {
                    return mid;
                }
            }
            return -1;
        };

        for (int i = 0; i < n; ++i) {
            if (i && nums[i] == nums[i - 1]) {
                continue;
            }
            if (binarySearch(i, nums[i] + k) != -1) {
                ++ans;
            }
        }

        return ans;
    }
};

复杂度分析

时间复杂度：$O(n\log{n})$
空间复杂度：$O(\log{n})$

题解3 - 排序+二分查找

基于题解2的分析，除了使用二分法之外，还可以用双指针。先将数组排序。左指针 $i$ 枚举数对中的较小值，右指针 $j$ 顺序查找数对中的较大值。

为了保证不重复计数，要跳过相同的数，利用数组的有序性，使用 i && nums[i - 1] == nums[i] 就可以判断。

代码

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        int ans = 0, n = nums.size();
        if (n == 1) return 0;

        sort(nums.begin(), nums.end());

        for (int i = 0, j = 1; i < n - 1 && j < n; ++i) {
            if (i && nums[i - 1] == nums[i]) continue;
            if (j <= i) j = i + 1;
            while (j < n && nums[j] < nums[i] + k) ++j;
            if (j < n && nums[j] == nums[i] + k) ++ans;
        }

        return ans;
    }
};