题目
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
1 | 给定 nums = [2, 7, 11, 15], target = 9 |
Related Topics
- 数组
- 哈希表
解法
暴力破解
两层循环遍历所有数进行比对
时间复杂度
:$T(n)=\frac{n^2-1}{2}$;$O(n)=n^2$空间复杂度
:$S(n)=3$;$O(n)=1$
1 | def twoSum(nums, target): |
暴击破解改进
由于原始的暴力破解需要对每一个前数计算后续的所有后数,现在优化为计算出每一个前数需要的后数,校验是否在nums
中
时间复杂度
:$O(n)=n^2$空间复杂度
:$O(n)=1$
1 | class Solution: |
建立HASH表–实际就是键值对
由于每次都去原数组(本质是链表)中查找很费时间,而且还存在重复的元素,可以对每一个独一无二的元素建立一个索引值。简单说就是字典查找比列表快。
通过遍历数组,每次计算target-nowNum是否在已遍历到的数中。由于已遍历的数已构成HASH表,所以查找时间很快。
时间复杂度
:$0(n)=n$空间复杂度
:$0(n)=n$
1 | class Solution: |