1. 为什么 STL 是 Hot100 的核心

刷 Hot100，本质上不是在考你会不会手写底层数据结构，
而是在考你能不能：

• 快速选对数据结构

• 用合适的容器存数据

• 高效完成查找、插入、删除、遍历

所以对刷题来说，STL 不是“语法附属品”，而是“主武器”。

你前期最重要的 STL 就这几个：

• vector：动态数组

• string：字符串

• pair：二元组

• unordered_map：哈希表

• unordered_set：哈希集合

• queue：队列

• stack：栈

把这些掌握好，Hot100 至少一半以上题型能进入正轨。

---

2. vector：刷题第一容器

---

2.1 vector 是什么

vector 可以理解成“长度可变的数组”。

和 C 语言数组相比，它的优点是：

• 不用提前固定大小

• 可以自动扩容

• 支持很多方便操作

• 能和 sort() 等算法直接配合

所以在 LeetCode 里，数组题基本都用 vector<int>。

---

2.2 定义方式

vector<int> nums;

表示一个整型动态数组。

常见初始化

vector<int> a;                  // 空数组
vector<int> b(5);               // 5个元素，默认都是0
vector<int> c(5, 1);            // 5个元素，都是1
vector<int> d = {1, 2, 3, 4};   // 直接初始化

---

2.3 常用操作

1）尾部插入

nums.push_back(10);
nums.push_back(20);

作用：把元素放到末尾。

---

2）访问元素

cout << nums[0] << "\n";
cout << nums[1] << "\n";

和数组一样，下标从 0 开始。

---

3）获取大小

cout << nums.size() << "\n";

注意：size() 返回的是元素个数。

---

4）判空

if (nums.empty()) {
    cout << "空数组\n";
}

---

5）删除末尾元素

nums.pop_back();

注意：pop_back() 没有返回值，只是删除最后一个元素。

---

6）最后一个元素

cout << nums.back() << "\n";

---

2.4 遍历 vector

写法 1：普通 for 循环

for (int i = 0; i < nums.size(); i++) {
    cout << nums[i] << " ";
}
cout << "\n";

这是最常见写法，尤其适合需要下标的时候。

---

写法 2：范围 for

for (int x : nums) {
    cout << x << " ";
}
cout << "\n";

适合只关心元素值，不关心下标。

---

2.5 二维 vector

Hot100 里会经常遇到二维数组，比如矩阵题。

vector<vector<int>> matrix;

初始化一个 3 行 4 列、全为 0 的矩阵

vector<vector<int>> matrix(3, vector<int>(4, 0));

访问元素

cout << matrix[1][2] << "\n";

---

2.6 vector 常见题型

vector 常用于：

• 数组题

• 双指针

• 二分查找

• 前缀和

• 滑动窗口

• 动态规划

• 矩阵题

---

2.7 vector 常见坑

坑 1：越界访问

vector<int> nums;
cout << nums[0];   // 错

空数组不能直接访问。

---

坑 2：pop_back() 前不判断是否为空

if (!nums.empty()) {
    nums.pop_back();
}

---

坑 3：把 size() 当成最后一个下标

长度是 n，最后一个下标是 n - 1。

---

2.8 刷题结论

数组题默认先想 vector<int>
矩阵题默认先想 vector<vector<int>>

---

3. string：字符串题核心容器

---

3.1 string 是什么

string 是 C++ 的字符串类型，比 char[] 好用很多。

string s = "hello";

---

3.2 常用操作

1）输入输出

string s;
cin >> s;
cout << s << "\n";

注意：cin >> s 默认读到空格结束。

---

2）长度

cout << s.size() << "\n";

---

3）访问字符

cout << s[0] << "\n";
cout << s[1] << "\n";

---

4）拼接

string s = "abc";
s += 'd';
s += "ef";
cout << s << "\n";   // abcdef

---

5）比较

string a = "abc";
string b = "abd";

if (a == b) cout << "相等\n";
if (a < b) cout << "a字典序更小\n";

---

6）截取子串

string s = "abcdef";
cout << s.substr(2, 3) << "\n";   // cde

含义：

• 从下标 2 开始

• 取长度为 3 的子串

---

3.3 遍历 string

写法 1：按下标遍历

for (int i = 0; i < s.size(); i++) {
    cout << s[i] << " ";
}
cout << "\n";

写法 2：范围 for

for (char c : s) {
    cout << c << " ";
}
cout << "\n";

---

3.4 修改字符

string s = "hello";
s[0] = 'H';
cout << s << "\n";   // Hello

---

3.5 字符串和数字互转

字符串转整数

string s = "123";
int x = stoi(s);

整数转字符串

int x = 123;
string s = to_string(x);

---

3.6 string 常见题型

• 最长无重复子串

• 最小覆盖子串

• 回文子串

• 字符统计

• 字符串模拟

• 括号匹配

• 字符串哈希基础题

---

3.7 string 常见坑

坑 1：把 string 当 C 风格字符串乱用

前期刷题尽量少碰 strlen()、strcpy() 这些 C 风格函数。

直接用：

• s.size()

• s[i]

• s.substr()

• s += ...

就够了。

---

坑 2：越界访问

string s = "";
cout << s[0];   // 错

---

3.8 刷题结论

字符串题的第一反应：string + 下标遍历

---

4. pair：存两个值的简单工具

---

4.1 pair 是什么

pair 可以把两个值放在一起。

pair<int, int> p = {1, 2};

访问方式：

cout << p.first << "\n";
cout << p.second << "\n";

---

4.2 为什么刷题常用

因为很多时候我们需要同时存两个东西，比如：

• 坐标 (x, y)

• 数值和下标 (value, index)

• 区间 (l, r)

---

4.3 常见写法

pair<int, int> p;
p.first = 10;
p.second = 20;

也可以：

pair<int, int> p = make_pair(10, 20);

---

4.4 pair 常出现在哪

1）vector 里放 pair

vector<pair<int, int>> vp;
vp.push_back({1, 2});
vp.push_back({3, 4});

2）queue 里放 pair

queue<pair<int, int>> q;
q.push({0, 0});

BFS 走网格图时特别常见。

3）unordered_map 的 value 里也可能放 pair

后面进阶时会见到。

---

4.5 刷题结论

需要同时保存两个相关信息时，先想 pair

---

5. unordered_map：哈希表核心武器

---

5.1 unordered_map 是什么

它是“键值对映射表”，也就是哈希表。

你可以理解为：

• 给一个 key

• 快速找到对应的 value

比如：

unordered_map<int, int> mp;
mp[1] = 100;
mp[2] = 200;
cout << mp[1] << "\n";   // 100

---

5.2 它为什么重要

Hot100 中很多经典题都离不开它：

• 两数之和

• 字母异位词分组

• 最长连续序列

• 和为 K 的子数组

• LRU 思想基础

• 出现次数统计

本质原因是：

哈希表能把“查找”从 O(n) 降到接近 O(1)

---

5.3 定义方式

key 是 int，value 是 int

unordered_map<int, int> mp;

key 是 char，value 是 int

unordered_map<char, int> mp;

key 是 string，value 是 int

unordered_map<string, int> mp;

---

5.4 常用操作

1）插入 / 修改

mp[1] = 10;
mp[2] = 20;

如果 key 不存在，就创建。
如果存在，就修改。

---

2）访问

cout << mp[1] << "\n";

---

3）统计次数

这是最经典用法。

string s = "aabca";
unordered_map<char, int> cnt;

for (char c : s) {
    cnt[c]++;
}

结果：

• a -> 3

• b -> 1

• c -> 1

---

4）判断是否存在

if (mp.find(1) != mp.end()) {
    cout << "存在\n";
}

解释：

• find(key) 找到就返回对应位置

• 找不到就返回 mp.end()

---

5）删除

mp.erase(1);

---

6）获取大小

cout << mp.size() << "\n";

---

5.5 遍历 unordered_map

for (auto& [key, value] : mp) {
    cout << key << " " << value << "\n";
}

如果你暂时不熟悉结构化绑定，也可以写：

for (auto& it : mp) {
    cout << it.first << " " << it.second << "\n";
}

前期建议你先记住第二种。

---

5.6 两数之和为什么用哈希表

题意简化：

给你数组 nums 和目标值 target，找两个数使它们和等于 target。

思路：

遍历到 nums[i] 时，去哈希表里看：

• 是否已经出现过 target - nums[i]

如果出现过，直接找到答案。

这个就是哈希表最经典的“边遍历边查找”。

---

5.7 unordered_map 常见题型

• 元素出现次数统计

• 查找某值是否出现过

• 前缀和 + 哈希

• 滑动窗口计数

• 建立值到下标映射

• 字符频率统计

---

5.8 unordered_map 常见坑

坑 1：把 mp[key] 当纯查询

if (mp[100]) ...

这个写法有风险。因为如果 100 不存在，mp[100] 会自动创建一个值为 0 的新元素。

更稳妥：

if (mp.find(100) != mp.end()) ...

---

坑 2：以为遍历顺序固定

unordered_map 是无序的，遍历顺序不固定。

---

5.9 刷题结论

一旦题目涉及“快速查找、计数、去重、映射”，先想哈希表

---

6. unordered_set：只存 key 的哈希集合

---

6.1 unordered_set 是什么

它和 unordered_map 类似，但只存值，不存键值对。

unordered_set<int> st;

你可以把它理解成：

只关心“某个元素存不存在”

---

6.2 常用操作

1）插入

st.insert(10);
st.insert(20);

2）判断是否存在

if (st.find(10) != st.end()) {
    cout << "存在\n";
}

3）删除

st.erase(10);

4）大小

cout << st.size() << "\n";

---

6.3 典型用途

1）判重

vector<int> nums = {1, 2, 3, 2};
unordered_set<int> st;

for (int x : nums) {
    if (st.find(x) != st.end()) {
        cout << "有重复元素\n";
        break;
    }
    st.insert(x);
}

2）去重

把数组元素放进集合中，就能保留不重复元素。

3）最长连续序列

Hot100 经典题。
用 unordered_set 判断某个数在不在集合里，非常高效。

---

6.4 和 unordered_map 的区别

• unordered_map：存 key -> value

• unordered_set：只存 key

---

6.5 刷题结论

只关心“在不在”，就优先想 unordered_set

---

7. queue：队列

---

7.1 queue 是什么

队列特点：

先进先出（FIFO）

就像排队。

queue<int> q;

---

7.2 常用操作

入队

q.push(1);
q.push(2);

取队头

cout << q.front() << "\n";

出队

q.pop();

判空

if (q.empty()) {
    cout << "空队列\n";
}

大小

cout << q.size() << "\n";

---

7.3 queue 在 Hot100 里的用途

最核心用途：

• BFS 广度优先搜索

• 二叉树层序遍历

• 图的最短步数问题

• 网格最短路径基础题

---

7.4 层序遍历为什么用 queue

因为层序遍历本质就是：

• 先处理当前层

• 再处理下一层

这和“先进先出”完全一致。

---

7.5 queue 常见坑

坑 1：pop() 没返回值

q.pop();

它只是删除，不返回元素。

想拿到队头元素要先：

int x = q.front();
q.pop();

---

7.6 刷题结论

只要看到 BFS、层序遍历，先想 queue

---

8. stack：栈

---

8.1 stack 是什么

栈特点：

后进先出（LIFO）

像叠盘子，后放上去的先拿出来。

stack<int> st;

---

8.2 常用操作

入栈

st.push(1);
st.push(2);

取栈顶

cout << st.top() << "\n";

出栈

st.pop();

判空

if (st.empty()) {
    cout << "空栈\n";
}

大小

cout << st.size() << "\n";

---

8.3 stack 在 Hot100 里的用途

• 有效括号

• 最小栈

• 单调栈

• 表达式计算

• 路径回退思想

---

8.4 有效括号为什么用栈

比如：

()[]{}

遍历时：

• 遇到左括号：入栈

• 遇到右括号：看栈顶是否匹配

因为括号匹配总是“最后出现的左括号，最先匹配”，
这正是栈的特点。

---

8.5 stack 常见坑

坑 1：空栈取 top

cout << st.top();   // 若为空会出错

所以一般要先判断：

if (!st.empty()) {
    cout << st.top() << "\n";
}

---

8.6 刷题结论

看到“匹配、最近、回退、单调性”，先想 stack

---

9. 这些容器怎么选

这是最关键的一节。

---

9.1 看到数组题

选：

vector<int>

---

9.2 看到字符串题

选：

string

---

9.3 看到需要同时存两个信息

选：

pair<int, int>

---

9.4 看到“快速查找某元素是否出现过”

选：

unordered_set

---

9.5 看到“某个值对应另一个值”

选：

unordered_map

比如：

• 数值 -> 下标

• 字符 -> 次数

• 前缀和 -> 出现次数

---

9.6 看到 BFS / 层序遍历

选：

queue

---

9.7 看到括号匹配 / 单调栈

选：

stack

---

10. STL 容器刷题模板

---

10.1 vector 模板

vector<int> nums = {1, 2, 3};
nums.push_back(4);

for (int i = 0; i < nums.size(); i++) {
    cout << nums[i] << " ";
}
cout << "\n";

---

10.2 string 模板

string s = "abcde";

for (int i = 0; i < s.size(); i++) {
    cout << s[i] << " ";
}
cout << "\n";

---

10.3 unordered_map 计数模板

unordered_map<char, int> cnt;

for (char c : s) {
    cnt[c]++;
}

---

10.4 unordered_set 判重模板

unordered_set<int> st;

for (int x : nums) {
    if (st.find(x) != st.end()) {
        cout << "重复\n";
    }
    st.insert(x);
}

---

10.5 queue 模板

queue<int> q;
q.push(1);
q.push(2);

while (!q.empty()) {
    int x = q.front();
    q.pop();
    cout << x << " ";
}

---

10.6 stack 模板

stack<int> st;
st.push(1);
st.push(2);

while (!st.empty()) {
    int x = st.top();
    st.pop();
    cout << x << " ";
}

---

11. 这几个 STL 的时间复杂度记忆

下面这些最好有印象。

---

11.1 vector

• 访问元素：O(1)

• 尾插：通常 O(1)

• 尾删：O(1)

---

11.2 unordered_map / unordered_set

• 插入：平均 O(1)

• 查找：平均 O(1)

• 删除：平均 O(1)

所以它们才是刷题中的高频武器。

---

11.3 queue / stack

• push()：O(1)

• pop()：O(1)

• front()/top()：O(1)

---

12. 现阶段你必须掌握到什么程度

你现在不需要做到“完全精通 STL”，
但至少要做到以下程度：

---

必会 1：vector

• 会定义

• 会遍历

• 会 push_back

• 会取大小

• 会访问元素

---

必会 2：string

• 会定义

• 会遍历

• 会取长度

• 会访问字符

• 会拼接

---

必会 3：unordered_map

• 会统计次数

• 会建立映射

• 会判断 key 是否存在

---

必会 4：unordered_set

• 会判重

• 会判断元素是否出现过

---

必会 5：queue 和 stack

• 会 push

• 会 pop

• 会 front / top

• 会 empty

---

13. 给自己的记忆口诀

可以直接背：

数组用 vector
字符串用 string
映射用 unordered_map
判重用 unordered_set
BFS 用 queue
匹配和单调性用 stack

再背一句：

只要题目想“查得快”，就要想到哈希

---

14. 本篇总结

这一篇你需要真正建立一个概念：

刷题不是先想语法，而是先想“我要用什么容器”

Hot100 中最重要的容器就是：

• vector

• string

• unordered_map

• unordered_set

• queue

• stack