目录
  1. 1. 题目
  2. 2. DEMO
  3. 3. 解法
    1. 3.1. 暴力破解
    2. 3.2. 暴击破解改进
    3. 3.3. 建立HASH表–实际就是键值对
TwoSum

题目

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

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

DEMO

1
2
3
4
5
> 给定 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$
  • LeetCode结果6436ms/12.5MB
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$
  • 空间复杂度:$O(n)=1$
  • LeetCode结果:828ms/12.5MB
1
2
3
4
5
def twoSum(nums, target):
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

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

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

  • 时间复杂度:不会算
  • 空间复杂度:$0(n)=n$
  • LeetCode结果:48ms/13.1MB
1
2
3
4
5
6
7
8
9
def twoSum(nums, target):
nums_dict = {}
for index, item in enumerate(nums):
result = target - item

if result in nums_dict and nums_dict[result] != index:
return [nums_dict[result], index]
else:
nums_dict[item] = index
文章作者: ZyTomorrow
文章链接: https://zytomorrow.top/2019/05/30/leetcode/twosum/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tomorrow
打赏
  • 微信
  • 支付寶

评论