python数组中的 k-diff 数对例题解析
作者:??盆友圈的小可爱???? 时间:2022-03-30 18:21:47
一、题目描述
题目内容:
题目示例:
题目解析:
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
首先对nums数组中的元素按照从低到高的顺序排列
在递增的数组中,由于双指针 i!=j,因此i指针一定是小于j的
枚举查找的判断的条件 nums[j] < nums[i]+k,指针j则往后移动
当nums[j] = nums[i] + k 时,则对数次数+1
三、总结
本题可以使用哈希方法要使用两个哈希表,属于牺牲空间换取效率。双指针方法,虽然没有用额外的空间,但是速度较于方法一慢一点。
我们用第一种方法,AC提交记录如下:
时间复杂度O(n),n为nums长度
空间复杂度O(n),需要使用哈希表,n为nums长度
来源:https://juejin.cn/post/7109863191928602637
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Go语言算法之寻找数组第二大元素的方法
laravel学习教程之存取器
MYSQL 数据库同步
一个ACCESS数据库数据传递的方法
Oracle 函数大全[字符串函数,数学函数,日期函数]第1/4页
asp 取一个数的整数 但不是四舍五入,只要有小数,就取大于这个数的整数
python入门:这篇文章带你直接学会python
![](https://img.aspxhome.com/file/2023/4/63174_0s.png)
PHP PDOStatement::bindColumn讲解
ASP利用TCPIP.DNS组件获得域名对应的IP
Sql Server 索引使用情况及优化的相关Sql语句分享
php中iconv函数使用方法
asp中数组的用法
go 判断两个 slice/struct/map 是否相等的实例
Asp.net清空控件值的方法(可自定义控件类型)
PHP常用函数和常见疑难问题解答
Oracle 常用的SQL语句
一个oracle指令的好网站
《写给大家看的设计书》阅读笔记之色彩
![](https://img.aspxhome.com/file/UploadPic/20097/30/color-85s.jpg)