Leetcode 1. 两数之和

发表于
| 字数统计: 654 | 阅读时长 ≈ 2

题目描述

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

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

示例:

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

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

分析

有这么几种办法

1. 暴力法

对于数组中的每一个数num，尝试在数组中找到另一个数target-num，时间复杂度$O(n^2)$

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i1, v1 in enumerate(nums):
            for i2, v2 in enumerate(nums):
                # 简单粗暴的判断
                if i1 != i2 and v1 + v2 == target:
                    return [i1, i2]

28 / 29 个通过测试用例

状态：超出时间限制

2. 排序后首尾指针

先将数组排序，之后设置i为第一个数j为最后一个数，计算i+j，如果大于target则说明j太大了需要向前挪一个，如果小于target说明i太小向后挪一个。

排序时间复杂度$O(nlogn)$，首尾指针扫描一次线性复杂度，最终复杂度$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums = sorted(enumerate(nums), key=lambda x:x[1])
        # 排序前 nums = [3,2,4]
        # 排序后 nums = [(1, 2), (0, 3), (2, 4)]
        # 就是在排序的时候记住之前的下标
        i, j = 0, len(nums) - 1
        while i < j:
            res = nums[i][1] + nums[j][1]
            # nums[i][1]取值
            if res > target:
                j -= 1
            elif res < target:
                i += 1
            elif res == target:
                return [nums[i][0], nums[j][0]]
                # nums[i][0]取排序前的下标

怎么这么快。。。

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

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

3. 哈希

使用一个哈希表，对于数组中的每个数，计算target-num并在哈希表中查找，如果找到则返回，没有找到就将num存入哈希表。

哈希表查找可近似为$O(1)$，因为只有一个循环，所以总体时间复杂度为$O(n)$。

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        # hashmap结构：{num: index}
        for index, num in enumerate(nums):
            another = target - num
            if another in hashmap:
                return [hashmap[another], index]
            hashmap[num] = index

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

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

为什么速度差不多呢，为什么用了哈希内存也一样呢