leetcode-1-两数之和

2020-08-27 约 984 字预计阅读 2 分钟

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例

1
2
3
4


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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/robot-return-to-origin

看着题目看似还是很简单，暴力模拟用二次循环就能做出来。时间复杂度：O(n^2), 空间复杂度：O(1)

唯一要注意下标边界越界问题，还有考虑清楚变量什么时候要加一，啥时候要减一。

但还是小看了这题。当nums很长时就会超时。一个长度为12599的测试用例耗时8秒多，这是不能忍受的。

题解1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def twoSum(self, nums, target: int):
        nums_len = len(nums)
        # 第一次循环
        for index, item in enumerate(nums):
            i = 0
            # 第二次循环
            for _ in range(nums_len-1):
                subscript = index + i + 1
                # 下标越界检查
                if subscript < nums_len:
                    if (item+nums[subscript]) == target:
                        return [ index, subscript]
                    else:
                        i = i + 1

忍不住偷瞄了下官方的题解，立即领悟了其中的奥妙：在一次遍历的时候， target 作为被减数，减去遍历的每一项。当判断两者的差flag存在列表nums时，就是解出答案的时刻。

题解2-0：

1
2
3
4
5
6


class Solution:
    def twoSum(self, nums, target: int):
        for index, item in enumerate(nums):
            flag = target - item
            if flag in nums:
                return [index, nums.index(flag)]

但是没考虑到减数和差为相同值的情况。在这个 nums = [3,2,4] target = 6 用例上栽倒了。即：要注意目标元素target - item 的值不能是nums[index]本身。在检测时打个屏蔽补丁就好了，见题解2-1。

题解2-1:

执行用时：1140 ms, 在所有 Python3 提交中击败了31.23%的用户

内存消耗：14.6 MB, 在所有 Python3 提交中击败了86.51%的用户

全程都在一个列表中完成，节省内存，但是 python 的 in list操作时间复杂度是O（n）,有什么更快的方法呢？

1
2
3
4
5
6
7
8
9


class Solution:
    def twoSum(self, nums, target: int):
        for index, item in enumerate(nums):
            flag = target - item
            nums[index] = '_'  # 屏蔽当前值
            if flag in nums:
                return [index, nums.index(flag)]
            else:
                nums[index] = item

题解3:

再偷瞄一眼官方题解,遍历一遍哈希表求的题解.一边检查目标元素一边将元素插入字典真秒不可言,效率刚刚地~仅用时56ms! python 的 in dict操作时间复杂度是O（1）

执行用时：56 ms, 在所有 Python3 提交中击败了97.24%的用户

内存消耗：15 MB, 在所有 Python3 提交中击败了46.71%的用户

1
2
3
4
5
6
7
8


class Solution:
def twoSum(self, nums, target: int):
    target_dic = {}
    for index, item in enumerate(nums):
        flag = target - item
        if flag in target_dic   :
            return [target_dic[flag], index]
        target_dic[item] = index  # 写在后面可以避免 题解2-0 发生的问题

目录

leetcode-1-两数之和

题目描述

示例