Leetcode 1:两数之和

发布时间:2019-10-15 09:05:16编辑:auto阅读(1420)

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

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

    示例:

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

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

    方法1,暴力解法。

    直接每一个元素都与自己之前的元素相加看是否有目标值,有就输出。

    代码如下:

    class Solution:
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            n = len(nums)
            for i in range(n):
                for j in range(i):
                    if nums[i] + nums[j] == target:
                        target_num = [i,j]
                        return target_num
            return None
    
    ​

    时间消耗和空间消耗如下:

    执行用时: 4500 ms, 在Two Sum的Python3提交中击败了32.72% 的用户

    内存消耗: 7.3 MB, 在Two Sum的Python3提交中击败了85.58% 的用户

    方法2,使用enumerate函数

    查看评论使用enumerate 函数效率更高。

    enumerate函数可以将一个数组转化为一个key从开始,值为数组对应元素的字典。

    代码如下:

    class Solution:
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            if not nums:
                return None
                d = dict()
            for i,item in enumerate(nums):
                tmp = target – item
                if tmp in d:
                    return [i, d[tmp]]
                    d[item] = i
            return None

    时间消耗和空间消耗如下:

    执行用时: 44 ms, 在Two Sum的Python3提交中击败了99.77% 的用户

    内存消耗: 7.9 MB, 在Two Sum的Python3提交中击败了46.97% 的用户

关键字