Python数组中k-diff数对问题解析：哈希表与双指针法

七月

发布时间：2026-10-15| 3人浏览过

原创

本文深入解析Python中求解数组k-diff数对的问题。通过哈希表法利用两个集合去重并统计差值，实现O(n)时间复杂度；同时介绍排序后双指针法，通过移动指针查找满足nums[j] - nums[i] = k的组合。文章对比两种方法的时空复杂度，提供完整Python代码实现及复杂度分析，帮助开发者掌握高效解题技巧。

一、题目描述

题目内容：

题目示例：

题目解析：

1 <= nums.length <= 104
-107 <= nums[i] <= 107
0 <= k <= 107

二、思路分析

面对本题，我们需要在一个整数数组中找出差值恰好为k的数对数量（即k-diff）。在着手编写代码前，必须明确几个关键约束条件：

数组nums中的所有元素均为整数。
数对中的两个元素索引i和j必须不同，即i不等于j。
k-diff数对的定义关系为：nums[i] - nums[j] = k，这等价于 nums[i] = nums[j] + k，或者 nums[i] - k = nums[j]。
需要注意的是，即使存在数值相同的数对（例如(1,3)和(3,1)），在最终结果中只应计算一次，即去重处理。

基于上述对题目的深入理解，特别是考虑到需要排除重复数对的情况，我们可以很自然地联想到使用哈希表（Hash Table）来构建解决方案。

方法一：构建哈希表

依据上述思路，我们可以使用Python代码快速实现该逻辑，具体代码如下：

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ans = set()
        numset = set()
        for num in nums:
            if num - k in numset:
                ans.add(num-k)
            if num + k in numset:
                ans.add(num)
            numset.add(num)
        return len(ans)

针对数对中可能出现的重复场景，例如示例一中差值k=1时，(1,3)与(3,1)被视为同一种情况，因此我们需要定义两个哈希表来分别存储和处理数据。
哈希表可以通过字典（key-value对）或集合（set）来实现。在本题中，由于我们只关心数值是否存在而不涉及具体的索引关系，因此可以定义ans和numset两个集合。
当遍历到的nums[i]大于nums[j]时，若nums[j] = nums[i] - k存在于numset中，则将较小的那个值（即nums[i]-k）加入ans集合。
当nums[i]小于nums[j]时，若nums[j] = nums[i] + k存在于numset中，则将较小的那个值（即nums[i]）加入ans集合。

方法二：双指针

基于上述思路，使用Python代码实现如下：

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        ans = 0
        j = 0
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i-1]:
                while j < len(nums) and (nums[j] < nums[i] + k or j <= i):
                    j +=1
                if j < len(nums) and nums[j] == nums[i] + k:
                    ans +=1
        return ans