Yefei.Blog

个人日记 WIKI

用户工具

站点工具


leetcode:001-two-sum

001: Two Sum

看到难度是 Easy 级别,又是第一题,应该难不倒我,没想到结果让人从入门到放弃的心痛感!解此题造成我失眠噩梦! 题目首先是给你一个数字数组nums,然后再给你一个数字target,这个数字是在数组nums的其中两个数字的和target,找出这两个数字在数组中的位置。 我首先想到的就是遍历 for a in nums 得出 v = target - a, 然后再去 nums 找这个数字的索引搞定! 我太天真的,这里会有个问题,不满足出题条件,就是不能使用同一个位置的数字。 比如 [3,1,3] 和为6 , 按照我这个算法,找出的结果肯定是 0,0 ,我再想能不每次找 v 的时候先排除 a 的位置, 问题是好像没有这个直接功能。

第一次尝试

天真的我自认为很高效,因为没有创建多余的变量,
结果却是重重的打脸!狠狠的一击!连通过都没有!直接报告超时!m(
可能循环次数太多了!

class Solution(object):
    def twoSum(self, nums, target):
        l = len(nums) - 1
        a = b = 0
        while True:
            if a != b and nums[a] + nums[b] == target:
                return [b, a]
            if a == l:
                a = 0
                b += 1
                if b == l:
                    break # 找不到结果跳出,防止死循环
            else:
                a += 1

第二次尝试

改进算法,减少循环,在每次循环查找第二个数位置的时候可以直接从a的起始位置开始
这次终于给通过了,但是结果超级不理想!排名只有 36%!!! 打脸打脸打脸!m(
直接原因就是使用了 in list 功能!因为 in list 操作是遍历列表,如果给定一个大列表势必会非常慢!

class Solution(object):
    def twoSum(self, nums, target):
        for a in nums:
            x1 = nums.index(a)
            v = target - a
            if v in nums[x1+1:]:
                return [x1, nums[x1+1:].index(v)+x1+1]

最后我有想过先把给定的数组先转换成字典,然后利用字典来检索位置,因为字典的查找方式是直接定位的,随便多大都行。
但是我觉得如果给定一个超大的列表,转换成字典势必会浪费性能浪费内存!
虽然是这样还是试了一下,时间果然比上一个算法缩短一倍以上。但是总觉得哪里不妥…

经过一晚上的折腾,是的没错,我本天真的以为睡前花5分钟做一题睡个好觉。结果折腾到早上5点!而且最终的结果非常不理想。
我心如刀割。我放弃折腾了,我想睡个好觉,我上网搜了别人的解法。 我心好累! :-|

别人的解法

class Solution(object):
    def twoSum(self, nums, target):
        process = {}
        for i in xrange(len(nums)):
            if target-nums[i] in process:
                return [process[target-nums[i]]+1, i+1]
            process[nums[i]] = i
leetcode/001-two-sum.txt · 最后更改: 2016/10/03 16:02 由 yefei