leetcode[1]-两数之和

题目

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

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

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

python代码:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)
        rlist=[]
        if length==0:
            return False
        for i in xrange(length-1): # n
            #print(nums[i+1:length])
            if (target-nums[i]) in nums[i+1:length]:
                rlist.append(i)
                rlist.append(nums[i+1:length].index(target-nums[i])+i+1)
                return rlist

首先呢,这道题的考点在于算法,因为你可以暴力解决,但显然有更高效的方法,所以我们就要想办法不去一次又一次的遍历整个列表,如果过一遍就能找到答案?或者更少的遍历?

if length==0:
    return False

这是排除掉极端情况,给的列表为空的时候,这也是最容易忽视的,虽然对于整个算法来说不是那么复杂,不是那么重要,但是没有它,你的算法一定会出bug。

for i in xrange(length-1):

用来遍历整个数组,因为你要找到整个数组中符合要求的索引,那么最优算法的最坏情况就是遍历一遍。

if (target-nums[i]) in nums[i+1:length]:

这句是算法的精髓,我们从头开始遍历整个列表,遇到一个元素使用in来判断一下target-nums[i]是否在剩下的列表中nums[i+1:length](想一下为什么是在剩余的列表中找,而不是在整个列表中),若没有,则可以肯定,当前的num[i]一定不是我们想要的,继续往后找,如果发现差值存在与列表的剩余部分,则现在我们已经找到了和为target的两个值,最后只需使用list.index(value),即可找到他们对应的索引。

rlist.append(i)
rlist.append(nums[i+1:length].index(target-nums[i])+i+1)

分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

延伸

上述解法容易想到的一个优化点就是listin操作的时间复杂度是O(n),所以我们可以更换成字典的in操作来降低时间复杂度。

class Solution(object):
    def twoSum(self, nums, target):
        length = len(nums)
        rlist={}
        if length==0:
            return False
        for i in range(length): #
            if (target-nums[i]) in rlist:
                return [i,rlist[target-nums[i]]]
            else:
               rlist[nums[i]] = i

分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

发表评论

电子邮件地址不会被公开。