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 提交。


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

查看所有标签

猜你喜欢:

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

文明之光 (第三册)

文明之光 (第三册)

吴军 / 人民邮电出版社 / 2015-1-1 / 59

【《文明之光》系列荣获由中宣部、中国图书评论学会和中央电视台联合推选的2014“中国好书”奖】 吴军博士从对人类文明产生了重大影响却在过去被忽略的历史故事里,选择了有意思的几十个片段特写,以人文和科技、经济结合的视角,有机地展现了一幅人类文明发展的宏大画卷。 《文明之光 》系列大致按照从地球诞生到近现代的顺序讲述了人类文明进程的各个阶段,每个章节相对独立,全景式地展现了人类文明发展历程......一起来看看 《文明之光 (第三册)》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

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

URL 编码/解码