0001. 两数之和 #
- 标签:数组、哈希表
- 难度:简单
题目大意 #
描述:给定一个整数数组 nums
和一个整数目标值 target
。
要求:在该数组中找出和为 target
的两个整数,并输出这两个整数的下标。可以按任意顺序返回答案。
说明:
- $2 \le nums.length \le 10^4$。
- $-10^9 \le nums[i] \le 10^9$。
- $-10^9 \le target \le 10^9$。
- 只会存在一个有效答案。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:枚举算法 #
- 使用两重循环枚举数组中每一个数
nums[i]
、nums[j]
,判断所有的nums[i] + nums[j]
是否等于target
。 - 如果出现
nums[i] + nums[j] == target
,则说明数组中存在和为target
的两个整数,将两个整数的下标i
、j
输出即可。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n^2)$
- 空间复杂度:$O(1)$。
思路 2:哈希表 #
哈希表中键值对信息为 target-nums[i] :i
。i
为下标。
- 遍历数组,对于每一个数
nums[i]
:- 先查找字典中是否存在
target - nums[i]
,存在则输出target - nums[i]
对应的下标和当前数组的下标i
。 - 不存在则在字典中存入
target-nums[i]
的下标i
。
- 先查找字典中是否存在
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$,其中 $n$ 是数组
nums
的元素数量。 - 空间复杂度:$O(n)$。