力扣热题100-----[1]两数之和---C++版
题目要求
//给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
//
// 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
//
// 你可以按任意顺序返回答案。
// 示例 1:
//
//
//输入:nums = [2,7,11,15], target = 9
//输出:[0,1]
//解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
//
//
// 示例 2:
//
//
//输入:nums = [3,2,4], target = 6
//输出:[1,2]
//
//
// 示例 3:
//
//
//输入:nums = [3,3], target = 6
//输出:[0,1]
//
//
//
//
// 提示:
//
//
// 2 <= nums.length <= 103
// -109 <= nums[i] <= 109
// -109 <= target <= 109
// 只会存在一个有效答案
常规基本解法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//unordered_map 内部实现了哈希表 可以用于快速搜索
// 头文件引入include<unordered_map>
unordered_map<int,int> hashtable;
for (int i = 0 ; i<nums.size();++i){
//auto 自动类型
// hashtable.find(target - nums[i]) 返回的是一个迭代器,通过second属性来获取值
//没找到就返回unordered_map::end
auto it = hashtable.find(nums[i]);
if(it != hashtable.end()){ //存在补数
//it->second 此时表中查到数据的原下标 value
// i 此时数据的下标
// it->first 为key
// cout<<it->first;
return {it->second, i };
// return [it->second, i];
}
//把补数塞进表内,便于查找
hashtable[target - nums[i]] = i;
}
//return {} c++11的问题
// 花括号{}代表一个空的vector<vector<int>>,size为0
return {};
}
};
哈希表解法过程
该题的解法过程与之前的Java版本类似
首先通过unordered_map<>
创建一个哈希表;
之后将补数塞进哈希表内
hashtable[target - nums[i]] = i;
通过 hashtable.find(nums[i])
寻找当前数所需要的补数
- auto 自动类型,根据赋值的类型自动转换
-
hashtable.find()
如果找到结果,返回的是一个迭代器,通过second(value)属性来获取值,没找到就返回unordered_map::end -
it != hashtable.end()
判定是否寻找到了值
通过这个题我学到的知识点
-
在C++11中,
return{}
可以直接返回一个空数组[]
,那么
return{3,4,5} -> [3,4,5]
-
unordered_map 是一个C++的容器,内部采用的是hash表结构,拥有快速检索功能,可能会经常使用。
参考博客:https://blog.csdn.net/lizhengze1117/article/details/96728468
-
Vector作为函数返回值、可以用于函数接收参数
使用vector<>来定义,大概是规范化使用,用于修改方便吧
vector<int>& nums
这里的&是引用的意思,这样就可以修改实参。
短期计划
虽然Java,C++,Python,C#,都会一点,但是确实没有一个算得上是精通的,所以希望通过算法的练习来渐渐熟悉C++ STL的使用,java还是用来用作开发语言。