C++ STL库之Vector简介及例题（哈希表）（一）
Vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。
特性1：顺序容器中的元素按照严格的线性顺序排列，可以通过元素的下标访问对应的元素。
特性2：支持对序列中的任意元素进行快速直接查询，可以在序列末尾相对快速地添加/删除元素的操作，所以不知道自己所需的数组大小时，可以用Vector以节约空间。
注意： Vector容器的用法有很多，内置算法函数也有很多，这里就不一一介绍了，就写一些常用的好理解的，如果后面遇到了我会在文章里具体解释。
一、初始化
使用vector容器时需要声明头文件#inlcude <vector>;
vector容器可以是多种数据形式例如int / char / string / 自定义类型 / 结构体类型等等
具体初始化方法如下代码及解释所示：
#include <vector> // 头文件 #include <vector>;
#include <iostream>
using namespace std;
int main() {
// 限制整形数组长度为10，默认值为0
vector<int> vec_int_limit(10);
// 不限制数组长度
vector<int> vec_int;
// 直接给数组赋值
vector<int> vec_int_nums{
1,2,3,4,5,6 };
// 建立string类型数组，长度为10，每个默认为"uhao"
vector<string> string_array(10, "uhao");
// 建立二维数组，可直接赋值
vector<vector<int>> two_array{
{
1,2,3},{
4,5,6} };
// 从原数组中取一段值赋值,goal_array数组结果是{6，5，4}
// 如下代码区间为：[ original_array.begin() , original.begin()+3 )
vector<int> original_array{
6,5,4,3,2,1 };
vector<int> goal_array(original_array.begin(),original_array.begin() + 3);
return 0;
}
二、数值操作
Vector容器有很多种函数可以对内容进行不同操作，这里就介绍一些常用的，后续用到别的会再解释。
创建一个数组并直接赋值：vector<int> vec{ 7,5,3,1,2,0 };
访问数组下标中的元素：vec[1]; // 二维数组同理vec[num1][num2]
获取数组下标中的元素，同 vec[1]：vec.at(1);
在尾部添加一个元素 8：vec.push_back(8);
删除最后一个元素：vec.pop_back();
获取vector数组元素个数，即长度：vec.size();
获取数组第一个元素的指针：vec.begin();
获取数组最后一个元素+1的指针：vec.end();
获取数组第一个元素值：vec.front();
获取数组最后一个元素值：vec.back();
与数组other_array交换数据(可以说是用other_array替换vec)：vec.swap(other_array);
判断是否为空，为空返回1，不为空返回0：vec.empty();
在第i+1个元素前插入数据e：vec.insert(vec.begin() + i , e);
在倒数第i个元素前面插入e：vec.insert(vec.end() - i , e);
例题
力扣经典第1题《两数之和》
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
题解
思路 1
用两个for循环，暴力破解，这个方法比较简单就不写解析了，代码如下：
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {
i, j};
}
}
}
return {
};
}
// 来源：力扣（LeetCode）
思路 2
用两个for循环的时间复杂度比较高，所以如果我们如果能够先确定一个数字，然后在数组余下的数字中迅速找出target-x，那么我们的效率肯定会翻倍；
所以我们这个时候就会想到**哈希表。**
哈希表简析
哈希表是一种数据结构，它可以提供非常快速的数据插入和查找操作。它通过一个叫做哈希函数的过程，将存储的数据项与一个特定的索引关联起来，这个索引指示了数据项在表中的位置。
C++哈希表初始化
#include <iostream>
#include <unordered_map> // 哈希表头文件
using namespace std;
int main()
{
unordered_map<int, int> hashMap; // 创建哈希表
// 进行赋值
hashMap[1] = 10;
hashMap[2] = 20;
hashMap[3] = 30;
// it->first 用于获取当前迭代器it指向的元素下标
// it->second 用于获取当前迭代器it指向的元素值
for (auto it = hashMap.begin(); it != hashMap.end(); it++) {
cout << "key:" << it->first << " value:" << it->second << endl;
}
/*
输出结果为：
key:1 value:10
key:2 value:20
key:3 value:30
*/
return 0;
}
C++哈希表基本操作
1. 插入操作
// 使用下标操作符插入元素
hashMap[key] = value;
// 使用insert()方法插入元素
hashMap.insert({
key, value});
2. 删除操作
hashMap.erase(key); // 删除指定元素key
3. 访问
hashMap[key]; // 直接访问 或用迭代器，见上哈希表简析代码
★4. 判断元素是否存在
// 方法1 根据哈希表的特性，如果一个元素被注册过也就是存在，则count值为1，否则为0
if(hashMap.count(key) > 0){
// 存在
}
else{
// 不存在
}
// 方法2 使用find函数，如果查找的key不存在于哈希表，则返回值与hashMap.end()相等，反之同理
if (hashMap.find(key) != hashMap.end()) {
cout << "存在";
}
else {
cout << "不存在";
}
大致了解了哈希表的应用之后，我们可以得出以下优化后的代码：
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
if (m.count(target - nums[i])) {
return {
m[target - nums[i]], i};
}
m[nums[i]] = i;
}
return {
};
}
代码解析
1. 创建一个空的哈希表 unordered_map<int, int> m; 用来存储数组值到索引的映射。
2. 使用一个for循环，遍历整个输入数组 nums。
3. 在循环内部，使用 if 语句检查哈希表中是否存在一个键值对，其键（target - nums[i]）是目标值与当前元素值的差。
4. 如果这样的键存在，说明我们找到了两个数，它们的和等于目标值：target - nums[i] 是之前某个元素的值，nums[i] 是当前元素的值。这时，我们返回一个包含两个下标的数组：先前元素的下标 m[target - nums[i]] 和当前元素的下标 i。
5. 如果没有找到，则将当前元素的值和它的下标 i 加入到哈希表中，即 m[nums[i]] = i;
6. 如果整个数组都遍历完了还没有找到这样的两个数，则函数返回一个空数组 return {};。
基本上，这段代码利用哈希表存储已经遍历过的元素的值和对应的下标，借助这个表我们能在O(1)的时间复杂度内查找到 target - nums[i]。因此，整个函数的时间复杂度是O(n)，其中n是数组 nums 的长度。这是一个高效的解决方案，因为它避免了使用两个嵌套循环，这在最坏的情况下会导致O(n^2)的时间复杂度。
