532.数组中的k-diff数对 Python&Java 哈希表、双指针双解

532.数组中的k-diff数对

https://leetcode.cn/problems/k-diff-pairs-in-an-array/solution/by-qingfengpython-jpv4/

难度：中等

题目：

给定一个整数数组和一个整数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.length <= 10 ^ 4
• -10 ^ 7 <= nums[i] <= 10 ^ 7
• 0 <= k <= 10 ^ 7

示例：

示例 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

分析

哈希表是第一时间会想到的方式，通过哈希表将数组进行压缩整合。
然后由于key值为数字默认已排序，可以直接循环keys查找满足条件的数对
由于k可能为0，所以循环时需要分两种情况判断即可：

1. k == 0 并且 key对应的value值大于1
2. k > 0 并且 key + k 在哈希表中

双指针的解题方式，是时间换空间的一种思路。

1. 先将数组进行排序
2. 初始右指针为1，然后通过l指针范围[0,length - 1]的范围进行for循环
3. 循环下标l为0 或者 nums[l] != nums[l - 1] 时满足检索要求
4. r < length - 1的前提下，当r
5. 在3、4完成的条件下判断nums[r] 是否等于 nums[l] + k

哈希表解题：

Python:

from collections import Counter
class Solution:
    def findPairs(self, nums, k):
        dic = Counter(nums)
        ret = 0
        for i in dic:
            if k == 0 and dic[i] > 1 or k > 0 and i + k in dic:
                ret += 1
        return ret
1
2
3
4
5
6
7
8
9

Java:

class Solution {
    public int findPairs(int[] nums, int k) {
        HashMap<Integer, Integer> d = new HashMap<>();
        int ret = 0;
        for (int num : nums) {
            d.put(num, d.getOrDefault(num, 0) + 1);
        }
        for (int key : d.keySet()) {
            if (k == 0 && d.get(key) > 1 || k > 0 && d.containsKey(key + k)) {
                ret++;
            }
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

双指针解题：

Python:

class Solution:
    def findPairs(self, nums, k):
        nums.sort()
        ret = 0
        r = 1
        for l in range(len(nums) - 1):
            if l == 0 or nums[l] != nums[l - 1]:
                while r < len(nums) - 1 and (r <= l or nums[r] - nums[l] < k):
                    r += 1
                if nums[l] == nums[r] - k:
                    ret += 1
        return ret
1
2
3
4
5
6
7
8
9
10
11
12

Java:

class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int ret = 0;
        int r = 1;
        for (int l = 0; l < nums.length - 1; l++) {
            if (l == 0 || nums[l] != nums[l -1]){
                while (r < nums.length - 1 && (r <= l || nums[r] < nums[l] + k)){
                    r++;
                }
                if (nums[r] == nums[l] + k) {
                    ret++;
                }
            }
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

欢迎关注我的公_众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown