532.数组中的k-diff数对

链接：532.数组中的k-diff数对
难度：Medium
标签：数组、哈希表、双指针、二分查找、排序
简介：给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

题解 1 - cpp

• 编辑时间：2022-06-16
• 执行用时：16ms
• 内存消耗：13.9MB
• 编程语言：cpp
• 解法介绍：排序后，针对于每个点查找差值为 k 的点的数量。

class Solution {
   public:
    int findPairs(vector<int> &nums, int k) {
        map<int, int> m;
        for (auto &num : nums) m[num]++;
        if (k == 0) return check0(m);
        int ans = 0;
        vector<int> list;
        for (auto &item : m) list.push_back(item.first);
        int n = list.size(), l1 = 0, l2 = 0;
        for (int r = 0; r < n; r++) {
            while (l2 < r && list[r] - list[l2] >= k) l2++;
            while (l1 < l2 && list[r] - list[l1] > k) l1++;
            ans += l2 - l1;
        }
        return ans;
    }
    int check0(map<int, int> &m) {
        int ans = 0;
        for (auto &item : m) {
            if (item.second > 1) ans++;
        }
        return ans;
    }
};