侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-16 / 0 评论 / 0 点赞 / 236 阅读 / 973 字
温馨提示:
本文最后更新于 2022-07-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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();
    }
}
0

评论区