数据结构与算法4 分钟 读完 (大约 588 个字)

两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例: 

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

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

题目来源：LeetCode。

题目解法

方法一：暴力法

暴力法就是遍历每个元素 x，并分别与其后面所有元素求和，求和的值与 target 值比较，相等则返回它们的下标。 

1
2
3
4
5
6
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(0, len(nums)):
            for j in range(i, len(nums)):
                if (nums[i] + nums[j]) == target:
                    return [i, j]

复杂度分析：

  • 时间复杂度：$O(n^2)$
    对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 $O(n)$ 的时间。因此时间复杂度为 $O(n^2)$。
  • 空间复杂度：$O(1)$

方法二：哈希表

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。保持数组中的每个元素与其索引相互对应的最好方法是哈希表。

迭代把元素插入到哈希表中，在遍历当前元素时检查表中是否已经存在与之所对应的目标元素。如果它存在，表示我们已经找到了对应解，立即将其返回。若不存在，则将其插入到哈希表中。 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}

        for i in range(0, len(nums)):
            diff = target - nums[i]

            # an element can't double use 
            if diff in hashmap.keys() and hashmap[diff] != i:
                return [hashmap[diff], i]
            else:
                hashmap[nums[i]] = i

复杂度分析：

  • 时间复杂度：$O(n)$
    我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 $O(1)$ 的时间。
  • 空间复杂度：$O(n)$
    所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
#

评论

×