文章目录
- 1.题目描述
- 示例
- 提示
- 2.解答思路
- (1)暴力解法
- (2)哈希表
- 3.实现代码
- 结果
- 4.总结
1.题目描述
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例
提示
- 2 <= nums.length <= 104
- 109 <= nums[i] <= 109
- 109 <= target <= 109
- 只会存在一个有效答案
2.解答思路
(1)暴力解法
脑海里最直接想到的是循环遍历两遍nums数组
直接判断循环条件符合时,即可返回相应的下标
(2)哈希表
用nums数组初始化哈希表hash
遍历nums数组,在哈希表中查找是否有target-nums[i]的键
查找到了就直接返回,若没查找到,继续遍历。
(因为提示的最后一条:只有一个唯一的答案)
相关代码所需知识
返回值可以使用
return {a,b};//列表list 支持表示返回值,也可以用于hash表初始化
哈希表相关:
unordered_map <int,int> hash;//定义一个无序哈希表
hash[nums[t]] =t ;//用 nums[t] 为键,索引 t 为值(因为find函数查找的是键,所以nums[t]必须放在键的位置,也就决定了不能使用有序哈希表map)
hash.find(a);//在哈希表的键中查找a值。
若查到,则返回相应的下标,若没有查找到,则返回hash.end()
auto it;//auto自动辨别返回值的类型。本题中it表示hash的一整个元素。
it->first 表示的是这个元素的key的值。
it->second 表示的是这个元素的value的值。
3.实现代码
//暴力解法
class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
int i, j;
for ( i = 0; i < nums.size(); ++i)
{
for ( j = i + 1; j < nums.size(); ++j)
{
if (nums[i] + nums[j] == target)
return {i, j};
}
}
return {i, j};
}
};
// 哈希表
class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
unordered_map<int, int> hash; // 有序哈希表,按键的从小到大排序
for (int t = 0; t < nums.size(); ++t)
{//用nums初始化哈希表
hash[nums[t]] =t ;//用nums[t]键,,索引t为值
}
for (int i = 0; i < nums.size(); ++i)
{
auto p = hash.find(target - nums[i]);//查找的是键
if (p != hash.end() && p->second != i)
//其中 p->second != i为了保证同一个元素不能出现两次。比如6=3+3,不能返回0,0
{ // 找到了对应的元素的键值
return {i, p->second};
}
}
return {0, 0};//保证必须有返回值,随便写的两个整数
}
};
结果
暴力解法
哈希表
4.总结
自己知道是返回两个下标,但不知道该怎么写
return {i, j} ; //这个返回的写法是学来的,
查看题解时发现使用哈希表来查找更加高效,后续学习会补上相关的笔记~
2024.2.5 已经补上哈希表解法的相关代码。
自信,坚持,upup