LeetCode题解 - 1. 两数之和

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

内容简介:给定一个整数数组你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

leetcode

题目描述:

给定一个整数数组 nums 和一个目标值 target ,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解题思路

1. 暴力解法

刚看完题目时,我第一个想到的是暴力解法,即遍历数组,当前数与后面位置的数字相加,看是否等于 target ,由此可以写出如下解:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(0, len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

此时的时间复杂度为$O(n^2)$,空间复杂度为$O(1)$。

那么有没有更快一点的方法?

2. 哈希表

暴力解法的第二次遍历可以改进下,引入哈希表,将所有数装入哈希表,此时在遍历数组时,查看 target-num 是否在哈希表中,此时代码如下:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    dict = {}
    for i in range(0, len(nums)):
        dict[nums[i]] = i
    for i in range(0, len(nums)):
        find = target - nums[i]
        if find in dict.keys() and i != dict[find]:
            return [dict[find], i]

哈希表的查找效率为$O(1)$,因此算法的时间复杂度为$O(n)$,由于引入哈希表,空间复杂度取决于数组的长度n,因此空间复杂度为$O(n)$,用空间换取时间。

这种方式有个问题,假如数组中有重复数字,那存入哈希表后,重复的数字就会被丢弃,如:nums = [2,3,3], target = 6,此时正解为[1,2],但由于哈希表中的项无重复,第二个 3 并不会存入哈希表,导致无解,下面看如何解决这个问题。

3. 哈希表-改进

上述方法是在将所有数字存入哈希表后,再遍历比较,导致重复值被丢弃。

可以继续改进下,遍历数组的同时,与已存入哈希表中的数据进行对比,若不存在再存入哈希表,这样就将比较阶段提前到哈希表的 put 动作之前,从而解决上述问题。

def twoSum(self, nums: List[int], target: int) -> List[int]:
    dict = {}
    for i in range(0, len(nums)):
        find = target - nums[i]
        if find in dict.keys() and i != dict[find]:
            return [dict[find], i]
        else:
            dict[nums[i]] = i

本文由花墨 创作,采用 知识共享署名4.0 国际许可协议进行许可

本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名

最后编辑时间为: Jul 2, 2019 at 07:07 pm


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

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

数据挖掘中的新方法:支持向量机

数据挖掘中的新方法:支持向量机

邓乃扬、田英杰 / 科学出版社 / 2004-6-10 / 53.00元

支持向量机是数据挖掘中的一个新方法。支持向量机能非常成功地处理回归问题(时间序列分析)和模式识别(分类问题、判别分析)等诸多问题,并可推广于预测和综合评价等领域,因此可应用于理科、工科和管理等多种学科。目前国际上支持向量机在理论研究和实际应用两方面都正处于飞速发展阶段。希望本书能促进它在我国的普及与提高。 本书对象既包括关心理论的研究工作者,也包括关心应用的实际工作者。对于有关领域的具有高等......一起来看看 《数据挖掘中的新方法:支持向量机》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

MD5 加密
MD5 加密

MD5 加密工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具