两数之和

两数之和

题目说明

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

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

示例:

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

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

解决方案

  1. 暴力法
    遍历每个元素x,并查找是否存在一个值与target - x相等的目标元素。

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

    复杂度分析:

    • 时间复杂度:O(n^2), 对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费O(n)的时间。因此时间复杂度为O(n^2)
    • 空间复杂度:O(1)
  2. 字典一次完成
    事实证明,我们可以一次完成。在进行迭代并将元素插入到字典中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    res = dict()
    for index, num in enumerate(nums):
    another_num = target - num
    if another_num in res:
    return [res[another_num], index]
    res[num] = index
    return None

    复杂度分析:

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

说明: 如果您有更好的解决方案或者本人写的有什么问题,请多多指教!