您现在的位置是:首页>全部文章全部文章 1.两数之和 2021年1月16日 21:51【算法】【LeetCode】193人已围观 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 这里给出几种方法。 #### 一. 暴力破解法: __思路:__通过两次遍历来判断两个元素和为target的结果 ```python class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ size = len(nums) for i in range(size): for j in range(i+1, size): if (nums[i] + nums[j]) == target: return [i, j] ``` ##### 复杂度分析: __时间复杂度__:O(n^2) 第一次遍历列表时间复杂度为O(n),第二次遍历的时间复杂度为O(n),嵌套的情况下时间复杂度为O(n^2) #### 二. 一遍哈希 __思路:__将nums通过enumerate函数转化为一个类似字典的数据类型,然后进行遍历,通过判断当前的值加起来为target的值是否存在字典里,如果存在,则返回字典的值与当前的键,如果不存在,则将当前的值当成键,当前的键作为对应的值保存到字典 ```python class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ keys = {} for k, v in enumerate(nums): n = target - v if n in keys: return [keys[n], k] else: keys[v] = k ``` __时间复杂度:__O(n) 遍历一次列表时间复杂度为O(n) 上一篇:Django DTL常用过滤器 下一篇:python多行注释规范 相关文章 文章评论 共有193条评论来说两句吧... 用户名: 阅读排行 使用Python识别验证码 Django DTL常用过滤器 python多行注释规范 python如何实现超长整数? 工厂模式之Python实现 通过无损压缩减少NumPy内存使用 1.两数之和 单例模式之Python实现 python海象运算符":="的三种用法 Python中"is"和"=="的区别 站长推荐 Django DTL常用过滤器 标签云 公告 python 验证码 Django DTL 过滤器 算法 LeetCode 规范 注释 设计模式 Linux Apache Numpy jupyter ctypes 站点信息 文章统计:16条 文章评论:2条 点赞统计: 24个 统计数据:百度统计 微信公众号:扫描二维码,关注我们 站点地图:SiteMap