[LeetCode] 1. Two Sum 题解

栏目: 编程工具 · 发布时间: 5年前

内容简介:给定一个整数数组你可以假设每组输入将会有一个解决方案,且数组中同一个数字只能使用一次

给定一个整数数组 nums 和一个目标数字 target ,要求返回数组中两个数字的 下标 ,且这两个数字加起来等于目标数字 target

你可以假设每组输入将会有一个解决方案,且数组中同一个数字只能使用一次

例子:

输入 nums = [2, 7, 11, 15], target = 9,
因为 nums[0] + nums[1] = 2 + 7 = 9,
所以 return [0, 1]。
复制代码

问题难度

Easy

解题思路

期望遍历一遍数组,就可以找到两个符合条件的数字,遍历过程中,每读到一个数字,需要完成两个动作:

  1. 查询「补数集合」,判断该数字的「补数」(目标数字减去该数)是否存在,如果存在,则返回补数和该数的下标
  2. 如果不存在,那么该数很可能是别的数的「补数」,将该数和下标放入「补数集合」中

可以看到「补数集合」是这里的关键,它要以尽可能快的速度完成:

  1. 查询某个补数是否存在
  2. 插入一个补数

这两个操作。

而我们都知道,对于这种需求,有一种数据结构可以达到 的时间复杂度,那就是哈希表,说到这里,我们就可以动手写代码了:

class Solution(object):    
    def twoSum(self, nums, target):
        complements = {}
        for i, x in enumerate(nums):
            if target - x in complements:
                return [complements[target - x], i]
            complements[x] = i
复制代码

以上, complements 是我们的「补数集合」,在 Python 中,字典(dict)数据结构就是用哈希表实现的,所以这里 complements 就定义为一个字典。

第 4 行我们依次遍历数组

第 5、6 行用来判断当前数的「补数」是否存在,如果存在则返回「补数」所在的下标和当前数的下标

第 7 行是在「补数」不存在的情况下,将当前数作为其他数的「补数」,连同下标一起插入到「补数集合」中

于是,上面代码就实现了通过遍历一次数组,就可以找到符合条件的两个数的下标,时间复杂度为 。

原题链接


以上所述就是小编给大家介绍的《[LeetCode] 1. Two Sum 题解》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C#图解教程

C#图解教程

索利斯 (Daniel M.Solis) / 姚琪琳、苏林、朱晔 / 人民邮电出版社 / 2013-7-1 / CNY 89.00

本书是广受赞誉的C# 图解教程的最新版本。作者在本书中创造了一种全新的可视化叙述方式,以图文并茂的形式、朴实简洁的文字,并辅以大量表格和代码示例,全面、直观地阐述了C# 语言的各种特性。新版本除了精心修订旧版内容外,还全面涵盖了C# 5.0 的新增特性,比如异步编程、调用者信息、case 表达式、带参数的泛型构造函数、支持null 类型运算等。通过本书,读者能够快速、深入理解C#,为自己的编程生涯......一起来看看 《C#图解教程》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试