0001. 两数之和 #
- 标签:数组、哈希表
- 难度:简单
题目大意 #
描述:给定一个整数数组 nums
和一个整数目标值 target
。
要求:在该数组中找出和为 target
的两个整数,并输出这两个整数的下标。
解题思路 #
思路 1:枚举算法 #
最简单的思路是枚举算法。使用两重循环枚举数组中每一个数 nums[i]
、nums[j]
。判断所有的 nums[i] + nums[j]
是否等于 target
。
- 如果出现
nums[i] + nums[j] == target
,则说明数组中存在和为target
的两个整数,将两个整数的下标i
、j
输出即可。
利用两重循环进行枚举的时间复杂度为 $O(n^2)$。
思路 2:哈希表 #
另一种思路是利用哈希表。哈希表中键值对信息为 target-nums[i] :i
。i
为下标。
- 遍历数组,对于每一个数
nums[i]
:- 先查找字典中是否存在
target - nums[i]
,存在则输出target - nums[i]
对应的下标和当前数组的下标i
。 - 不存在则在字典中存入
target-nums[i]
的下标i
。
- 先查找字典中是否存在
利用哈希表求解的时间复杂度为 $O(n)$。
代码 #
思路 1 代码: #
|
|
思路 2 代码: #
|
|