【暴力, 模拟, 哈希表, 有序集合】 数组中的 k-diff 数对

题目

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，但我们只应返回不同的数对的数量。

示例 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

解题

方法一：哈希表

思路

首先考虑特殊情况：当 k == 0 时，问题就变成了求数组中有多少组重复元素，维护一个哈希表记录每个元素及其出现次数，循环数组更新哈希表，在某个元素出现第二次时把计数器(ans)自增，最后返回 ans 即可。

对于更加一般的情况：首先把所有元素去重放入列表中，两层循环对于列表中每个元素把它和之后的每个元素作差，如果差的绝对值等于 k 就把计数器(count)自增，最后返回 count 即可。

代码

class Solution {
    public int findPairs(int[] nums, int k) {
        if (k == 0) {
            Map<Integer, Integer> map = new HashMap<>();
            int ans = 0;
            for (int num : nums) {
                int count = map.getOrDefault(num, 0) + 1;
                map.put(num, count);
                if (count == 2) ans++;
            }
            return ans;
        }
        List<Integer> list = new ArrayList<>(new HashSet<>() {{
            for (int num : nums) this.add(num);
        }});
        int n = list.size(), count = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(list.get(j) - list.get(i)) == k) count++;
            }
        }
        return count;
    }
}

优化

在处理数组时都去重了为何不用树集顺便排个序？排序后还可以顺便剪个枝：如果内层循环某次算出的差值 diff 大于 k 就没必要继续循环了，直接 break 掉去判断下一个元素。

class Solution {
    public int findPairs(int[] nums, int k) {
        if (k == 0) {
            Map<Integer, Integer> map = new HashMap<>();
            int ans = 0;
            for (int num : nums) {
                int count = map.getOrDefault(num, 0) + 1;
                map.put(num, count);
                if (count == 2) ans++;
            }
            return ans;
        }
        List<Integer> list = new ArrayList<>(new TreeSet<>() {{
            for (int num : nums) this.add(num);
        }});
        int n = list.size(), count = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = list.get(j) - list.get(i);
                if (diff == k) count++;
                else if (diff > k) break;
            }
        }
        return count;
    }
}

方法二：哈希表

思路

维护两个集合 visited 存储之前已经遍历过的元素，ans 存储 k-diff 数对中较大的元素。

遍历数组，对于其中每个元素 num：

• 如果在 visited 集合中可以找到 num - k ，说明 num 作为一组 k-diff 数对中较大的元素存在，把它加入 ans 集合。
• 如果在 visited 集合中可以找到 num + k ，说明 num 作为一组 k-diff 数对中较小的元素存在，把跟它成一对的较大元素 num + k 加入 ans 集合。
• 把 num 加入 visited 集合表示已经遍历过。

代码

class Solution {
    public int findPairs(int[] nums, int k) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> ans = new HashSet<>();
        for (int num : nums) {
            if (visited.contains(num - k)) ans.add(num);
            if (visited.contains(num + k)) ans.add(num + k);
            visited.add(num);
        }
        return ans.size();
    }
}