LeetCode如何找出和为s的两个数字
发表于:2024-10-16 作者:千家信息网编辑
千家信息网最后更新 2024年10月16日,这篇文章主要为大家展示了"LeetCode如何找出和为s的两个数字",内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下"LeetCode如何找出和为s的两个数字"
千家信息网最后更新 2024年10月16日LeetCode如何找出和为s的两个数字
这篇文章主要为大家展示了"LeetCode如何找出和为s的两个数字",内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下"LeetCode如何找出和为s的两个数字"这篇文章吧。
题目描述
输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,则输出任意一对即可。
1 <= nums.length <= 10^5 1 <= nums[i] <= 10^6
题目样例
示例
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]
题目思考
如何利用递增排序的条件? 如何做到空间复杂度是 O(1)?
解决方案
思路
一个比较容易想到的思路是使用一个集合, 然后遍历一遍数组: 如果 target-当前的数
已经在集合的话, 就说明找到了一对结果, 直接返回即可; 否则就把当前的数加入集合但这个思路没有利用到递增排序的条件, 且使用了额外的空间, 并不是最优解 如何利用排序的条件呢? 通常有两种思路: 二分或者双指针 这里如果使用二分的话, 意味着固定当前的数为起点, 然后二分查找右侧区间 target-当前的数
是否存在, 会额外引入 logN 的时间复杂度, 还没有上面的思路好所以尝试使用双指针的做法, 将两个下标 i 和 j 初始化为数组的头和尾, 然后往中间靠拢 根据当前的和, 具体分为以下三种情况: nums[i] + nums[j] == target
: 找到一对满足条件的数字了, 直接返回nums[i] + nums[j] < target
: 当前和小于 target, 因为数组有序, 如果保留 nums[i], 而 j 继续往左的话, 新的和肯定更小于 target, 所以 nums[i]可以被安全排除, 即 i 直接加 1nums[i] + nums[j] > target
: 当前和大于 target, 因为数组有序, 如果保留 nums[j], 而 i 继续往右的话, 新的和肯定更大于 target, 所以 nums[j]可以被安全排除, 即 j 直接减 1这样遍历下去最终肯定 i 和 j 会相遇, 此时退出循环, 说明没找到满足条件的数字对, 返回空数组即可 使用双指针做法后, 时间复杂度没有变差, 也不需要额外的空间了
复杂度
时间复杂度 O(N): 只遍历了一遍数组 空间复杂度 O(1): 只使用了几个变量
代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 双指针
i, j = 0, len(nums) - 1
while i < j:
if nums[i] + nums[j] == target:
# 找到一对满足条件的数字, 直接返回
return [nums[i], nums[j]]
elif nums[i] + nums[j] < target:
# 当前和小于target, 只能是i向右移, 这样后续和才会更大
i += 1
else:
# 当前和大于target, 只能是j向左移, 这样后续和才会更小
j -= 1
return []
以上是"LeetCode如何找出和为s的两个数字"这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注行业资讯频道!
数字
数组
复杂
复杂度
条件
两个
思路
指针
空间
排序
内容
时间
篇文章
题目
肯定
输入
输出
有序
安全
做法
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
国家的数据库管理系统
网络安全信息系统等级保护
服务器桥接
济南口碑好的存储服务器批发
上海本地网络技术采购信息
海南综合软件开发服务价格
网络技术人员个人总结
ff14如何调服务器
游戏总修复数据库
二层网络技术说明
数据库按模型分类
太原2u服务器价格
云时空数据库免费
数据库设置数据自动增长
超星电子图书馆数据库
怎么看网站是否调用数据库
中专计算机网络技术知识点
苏州智能化联想服务器服务商
网络安全脆弱性因果
请简述软件开发文档
网络安全法律法图片
服务器怎么做网段互通
青浦区会计软件开发市场价
java数据库中文查询
查询数据库所有值
省长 网络安全和信息化
网络安全教育内容什么意思
服务器软件平台的形式
创建数据库的密码
linux服务器关闭