关于程序员:532-数组中的-kdiff-数对中等

这是 LeetCode 上的 532. 数组中的 k-diff 数对 ，难度为中等。

Tag :「哈希表」、「离散化」、「二分」、「双指针」

给定一个整数数组和一个整数 $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)。

提醒：

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

一个简略的想法是先应用「哈希表」进行计数。

对于每个 $x = nums[i]$ 而言，依据 $k$ 是否为 $0$ 进行分状况探讨：

$k$ 为 $0$：此时只能 $(x, x)$ 组成数对，此时判断 $nums[i]$ 呈现次数是否大于 $1$ 次，若满足则进行计数加一；
$k$ 不为 $0$：此时 $x$ 可能与 $a = x – k$ 或 $b = x + k$ 组成数对，别离查问 $a$ 和 $b$ 是否呈现过，若呈现过则进行计数加一。

为了避免雷同的 $x$ 进行反复计数，咱们须要统计完 $x$ 后，清空其呈现次数。

代码：

class Solution {public int findPairs(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        int ans = 0;
        for (int i : nums) {if (map.get(i) == 0) continue;
            if (k == 0) {if (map.get(i) > 1) ans++;
            } else {
                int a = i - k, b = i + k;
                if (map.getOrDefault(a, 0) > 0) ans++;
                if (map.getOrDefault(b, 0) > 0) ans++;
            }
            map.put(i, 0);
        }
        return ans;
    }
}

工夫复杂度：$O(n)$
空间复杂度：$O(n)$

咱们晓得能够应用「数组」充当「哈希表」来缩小常数，但因为 $nums[i]$ 的值域大小为 $2 \times 10^7$，可能会有 MLE 危险。

咱们须要对 $nums$ 进行离散化，预处理出一个去重且有序的数组 list。

在统计答案时，咱们不再须要在 nums 根底上统计，而能够间接在去重数组 list 上进行统计，同时将对「数值」的统计操作转换为对「下标」的统计操作。

代码：

class Solution {static int[] cnt = new int[10010];
    List<Integer> list;
    int find(int x) {int n = list.size(), l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return list.get(r) == x ? r : -1;
    }
    public int findPairs(int[] nums, int k) {Arrays.sort(nums);
        list = new ArrayList<>();
        for (int i : nums) {if (list.isEmpty() || i != list.get(list.size() - 1)) list.add(i);
        }
        Arrays.fill(cnt, 0);
        for (int i : nums) cnt[find(i)]++;
        int ans = 0, idx = 0;
        for (int i : list) {if (k == 0) {if (cnt[idx] > 1) ans++;
            } else {int a = find(i - k), b = find(i + k);
                if (a != -1 && cnt[a] > 0) ans++;
                if (b != -1 && cnt[b] > 0) ans++;
            }
            cnt[idx++] = 0;
        }
        return ans;
    }
}

工夫复杂度：排序离散化复杂度为 $O(n\log{n})$，统计答案复杂度为 $O(n\log{n})$。整体复杂度为 $O(n\log{n})$
空间复杂度：$O(n)$

跟进一步的，对于 $x = nums[i]$ 而言，咱们每次都在整段的 list 中二分找 $a = nums[i] – k$ 和 $b = nums[i] + k$ 的下标，导致咱们统计 $nums[i]$ 对答案的奉献时复杂度为 $O(\log{n})$，统计所有 $nums[i]$ 对答案的奉献为 $O(n\log{n})$。

实际上，利用 list 自身的有序性，咱们在从前往后解决每个 $nums[idx]$ 时，对应的 $a$ 和 $b$ 也必然是逐渐增大，因而咱们能够应用「双指针」来防止「二分」操作，使得统计所有 $nums[i]$ 对答案奉献的复杂度从 $O(n\log{n})$ 降落到 $O(n)$。

代码：

class Solution {static int[] cnt = new int[10010];
    public int findPairs(int[] nums, int k) {Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        for (int i : nums) {if (list.isEmpty() || i != list.get(list.size() - 1)) list.add(i);
        }
        Arrays.fill(cnt, 0);
        for (int i = 0, j = 0; i < nums.length; i++) {if (nums[i] != list.get(j)) j++;
            cnt[j]++;
        }
        int n = list.size(), idx = 0, ans = 0, l = 0, r = 0;
        for (int i : list) {if (k == 0) {if (cnt[idx] > 1) ans++;
            } else {
                int a = i - k, b = i + k;
                while (l < n && list.get(l) < a) l++;
                while (r < n && list.get(r) < b) r++;
                if (l < n && list.get(l) == a && cnt[l] > 0) ans++;
                if (r < n && list.get(r) == b && cnt[r] > 0) ans++;
            }
            cnt[idx++] = 0;
        }
        return ans;
    }
}

工夫复杂度：排序离散化复杂度为 $O(n\log{n})$，统计答案复杂度为 $O(n)$，整体复杂度为 $O(n\log{n})$
空间复杂度：$O(n)$

这是咱们「刷穿 LeetCode」系列文章的第 No.532 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

本文由 mdnice 多平台公布

关于程序员:532-数组中的-kdiff-数对中等

题目形容

哈希表

离散化 + 二分

离散化 + 双指针

最初