您现在的位置是：网站首页> 编程资料编程资料

python数组中的 k-diff 数对例题解析_python_

2023-05-26 373人已围观

简介 python数组中的 k-diff 数对例题解析_python_

一、题目描述

题目内容：

题目示例：

题目解析：

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

二、思路分析

我们拿到本题，读取题意要求在一组整数数组中，求出差值为k的数对对数k-diff。在思考如何解答该题之前，需要明确如下几点细节：

nums数组元素都是整数
索引位置i与位置j,不能相等
k-diff数对关系：nums[i] - nums[j] = k -> nums[i] = nums[j] + k -〉 nums[i] - k = nums[j]
k-diff数对，存在相同数对情况，但结果只取1次

因此，我们的对题目中进行详细了解了，因为会排除重复的数对，我们很容易想哈希表来构建

方法一：构建哈希表

根据上述思路，我们使用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)视为一种情况，则要定义两个哈希表来储存
哈希表可以通过字典k-value或者集合set(),本题无需考虑索引关系定义ans,numset两个集合
当 nums[i] > nums[j],则nums[j] = nums[i] - k在numset中，取最小的那一个则ans.add(nums[i]-k),
当 nuns[i] < nums[j],则nums[j] = nums[i] + k 在numset中，取较小的那一个则ans.add(nums[i])

方法二：双指针

根据上述思路，使用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