数组中的 k-diff 数对

标签: 数组 哈希表 双指针 二分查找 排序

难度: Medium

给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。

k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：

  • 0 <= i, j < nums.length
  • i != j
  • |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 <= 104
  • -107 <= nums[i] <= 107
  • 0 <= k <= 107

Submission

运行时间: 24 ms

内存: 17.7 MB

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        from collections import Counter
        if k == 0:
            return len(Counter(nums) - Counter(set(nums)))

            
        nums = set(nums)

        t = list(map(lambda x: x+k, nums))
        

        count = 0

        for i in t:
            if i in nums:
                count += 1
        
        return count

Explain

该题解的思路是首先判断k是否为0，如果k为0，则直接统计nums中出现次数大于1的元素个数并返回。如果k不为0，则先将nums去重，然后遍历nums中的每个元素x，判断x+k是否也在nums中，如果在则将count加1，最后返回count的值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        from collections import Counter
        
        # 如果k为0，则直接统计nums中出现次数大于1的元素个数并返回
        if k == 0:
            return len(Counter(nums) - Counter(set(nums)))

        # 将nums去重 
        nums = set(nums)

        # 遍历nums中的每个元素x，判断x+k是否也在nums中
        t = list(map(lambda x: x+k, nums))
        
        count = 0

        for i in t:
            if i in nums:
                count += 1
        
        return count

Explore

在k为0的条件下，需要统计数组中相同元素的出现次数，并且只有当某个元素出现至少两次时，这个元素才能形成k-diff数对（其中两个数相同）。Counter类是一个专门用来计数的数据结构，它可以直接统计数组中每个元素的出现次数，从而方便地找出出现次数大于1的元素。使用Counter可以非常简洁和直观地实现这一功能，而其他方法（如使用普通字典手动计数或使用多次遍历数组）可能会更加繁琐且容易出错。

将nums转换为set进行去重是为了确保每个数字在判断时只被计算一次，从而确保数对的唯一性。在k不为0的情况下，如果数组中有重复元素，不去重可能会导致某些数对被重复计算。例如，对于数组[1, 1, 2, 3]和k=1，如果不去重，数字1可能会重复计算数对(1,2)。而使用set去重后，每个元素只保留一次，可以保证每个数对只被计算一次，从而保持数对的唯一性。

题解中提到的逻辑确实考虑了k为负数的情况，因为无论k是正数还是负数，计算x+k的结果只要在nums中即可计为有效的数对。例如，对于数组[1, 2, 3, 4]和k=-1，数对(2,1)和(3,2)等都是有效的。因此，k的正负不影响算法的有效性，只是改变了数对的组成方式（对于正k是(x, x+k)，对于负k是(x, x-k)）。

使用`lambda`函数和`map`可以使代码更加简洁和函数式编程风格，有助于减少代码量并可能提高代码的可读性。然而，这种方法可能会比直接使用循环在性能上略有不足，因为`map`和`lambda`会创建额外的函数调用开销，并且生成的是一个列表而不是一个迭代器，这在处理非常大的数据集时可能会增加内存消耗。直接使用循环则更直接，可能在性能上更优，特别是在需要最佳性能或处理大数据时。