LeetCode 第1题:Two Sum

栏目: Python · 发布时间: 6年前

内容简介:给出一个整数数组,找出其中的两个整数,使相加等于指定整数,并返回这两个整数的索引。假设每组输入只有一种解法,并且不能重复使用同一个元素。举例:

题目

给出一个整数数组,找出其中的两个整数,使相加等于指定整数,并返回这两个整数的索引。

假设每组输入只有一种解法,并且不能重复使用同一个元素。

举例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9,
所以返回 [0, 1].

思路

最简单也是最直接的想法就是两重循环直接遍历计算就能得到结果,时间复杂度为 LeetCode 第1题:Two Sum

但这肯定不是最优解。

题目中提到只会有一种解法,那就意味着不会有重复的整数,不然就会有多解。

既然没有重复的,那用一个哈希来存储数据就最合适了,整数为键,索引为值。

那我们要找两个整数的索引就很方便了,在遍历数组的时候,检查和目标的差值是否在哈希中,有的话就是答案了。

Go 实现

func twoSum(nums []int, target int) []int {
    h := make(map[int]int)
    for i, value := range nums {
        if wanted, ok := h[value]; ok {
            return []int{wanted, i}
        } else {
            h[target-value] = i
        }
    }
    return nil
}

运行时间:4ms,超过100%的 golang 提交。

Python3 重写

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        h = {}
        for i, value in enumerate(nums):
            if value in h:
                return [h[value], i]
            else:
                h[target - value] = i
        return None

运行时间:52ms,超过47.04%的 python 3 提交。

Python3 优化

从上面的数据上看效率有点低,应该是 enumerate 生成迭代器效率稍差,所以换用 range(len(...)) 的写法。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        h = {}
        for i in range(len(nums)):
            value = nums[i]
            if value in h:
                return [h[value], i]
            else:
                h[target - value] = i
        return None

运行时间:36ms,超过99.71%的 python3 提交。


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

查看所有标签

猜你喜欢:

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

编程大师访谈录

编程大师访谈录

Susan Lammers / 李琳骁、吴咏炜、张菁 / 人民邮电出版社 / 2012-1 / 59.00元

《编程大师访谈录》是对19位计算机行业先驱的采访实录,采访对象包括查尔斯•西蒙尼、比尔•盖茨、安迪•赫兹菲尔德、雷•奥奇、杰夫•拉斯金等。访谈涉及他们软件创造过程的灵感、技术、编程习惯、动机、反思,以及对未来软件的畅想等。问答中集结了这些计算机先驱的精辟言论,处处闪烁着智慧的火花。 《编程大师访谈录》适合IT从业人员阅读。一起来看看 《编程大师访谈录》 这本书的介绍吧!

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

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具