题目

给定一个整数数组 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