题目

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
  • 数组
  • 哈希表

解法

暴力破解

两层循环遍历所有数进行比对

  • 时间复杂度：$T(n)=\frac{n^2-1}{2}$;$O(n)=n^2$
  • 空间复杂度：$S(n)=3$;$O(n)=1$
1
2
3
4
5
def twoSum(nums, target):
    for i in range(len(nums)-1):
        for j in range(len(nums)):
            if nums[i] + nums[j] == target:
                return i, j

暴击破解改进

由于原始的暴力破解需要对每一个前数计算后续的所有后数，现在优化为计算出每一个前数需要的后数，校验是否在nums中

  • 时间复杂度:$O(n)=n^2$
  • 空间复杂度:$O(n)=1$
1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            result = target - nums[i]
            if result in nums[i + 1:]:
                return i, nums[i + 1:].index(result) + i + 1

# runtime:848 ms
# memory:14.1 MB

建立HASH表–实际就是键值对

由于每次都去原数组(本质是链表)中查找很费时间，而且还存在重复的元素，可以对每一个独一无二的元素建立一个索引值。简单说就是字典查找比列表快。

通过遍历数组，每次计算target-nowNum是否在已遍历到的数中。由于已遍历的数已构成HASH表，所以查找时间很快。

  • 时间复杂度:$0(n)=n$
  • 空间复杂度:$0(n)=n$
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoSum(self, nums, target):
        tmpDict = {}
        for idx, num in enumerate(nums):
            tmpNum = target - num
            if tmpNum in tmpDict:
                return [tmpDict[tmpNum], idx]
            tmpDict[num] = idx

# runtime:44 ms
# memory:14.4 MB