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
猜你喜欢
- 无论是公司的同事还是外界的程序员朋友们,大部分人对JavaScript的高级应用不甚了解,已有的知识架构里会认为JavaScript仅仅是一
- perl - Practical Extraction and Report Language,Perl有很多命令行参数,通过它可以让你的程
- 代码如下:'============================== '格式化HTML,SDCMS加强版 '==
- 本文给大家介绍PHP中Http协议post请求参数,具体内容如下所示:WEB开发中信息基本全是在POST与GET请求与响应中进行,GET因其
- 一.权限表mysql数据库中的3个权限表:user 、db、 host权限表的存取过程是:1)先从user表中的host、 user、 pa
- 严格控制Session可以将不需要Session的内容(比如帮助画面,访问者区域,等等)移动到关闭Session的独立ASP应用程序中。在基
- 404错误,很多人都知道,如果要访问的url不存在的时候就读取显示这个页面.以往在处理404方面我们通常的做法是要麽简单写几行字,而有心人士
- 用户登录验证脚本,Chkpwd.asp<% '=======用户登录验证脚本======= '如果尚未定义Passed
- 本文实例讲述了Python反射和内置方法重写操作。分享给大家供大家参考,具体如下:isinstance和issubclassisinstan
- ''推拉门''动效也可以称作"手风琴"效果,大多数效果实现的思路基本是一样的,下面介绍两
- 用过软件的朋友都知道,进度条是一个优秀软件的重要组成部分。它的存在能够使用户及时掌握程序的运行进度,确认应用程序正常工作。可是ASP中似乎没
- ASP.net处理文件上传就简单的多了,我呢也是在学习中,顺便写写学习笔记。 先在表单中添加enctype="multipart/
- PyCharm 应该是大多数 python 开发者的首选 IDE,每天我们都在上面敲着熟悉的代码,写出一个又一个奇妙的功能。它是帮助用户在使
- match()函数的使用。以及从文本中提取数据的方法。在学习re模块的相关函数前应了解正则表达式的特殊字符准备一个要爬取的文本文档:直接从某
- 在介绍GROUP BY 和 HAVING 子句前,我们必需先讲讲sql语言中一种特殊的函数:聚合函数,例如SUM, COUNT, MAX,
- JavaScript: <script type="text/javascript"> var level1
- 今天我们继续向大家介绍一款翻页效果的制作。当鼠标移动到链接上时,翻页的链接区除了有悬停效果,还会放大。这样的效果具有很强烈的效果。大家适当美
- 利用python+ffmpeg合并B站视频及格式转换 B站客户端下载的视频一般有两种格式:早期的多为blv格式(由flv格式转换而来,音视频
- myisam_max_[extra]_sort_file_size足够大delay_key_write减少io,提高写入性能bulk_ins
- Dreamweaver快捷键大全,记住一些常用的快捷键会大大提高你的网页设计效率,如果你都使用快捷键,那么如果你去面试工作就容易被录取,呵呵