LeetCode C++ 笔记

这份笔记用于整理刷 LeetCode 过程中常用的 C++ 语法、STL、算法模板、数据结构、典型题型和高频易错点。

目标不是罗列所有知识点，而是建立一套做题时能快速检索、复习时能快速回忆、面试时能清楚表达的知识框架。

一、C++ 与 STL 基础

这一部分主要整理 LeetCode 里最常用的 C++ 工具。重点记录三类内容：

常用调用方法
底层数据结构
时间复杂度与适用场景

1. `std::string`

1）它是什么

std::string 是 C++ 标准库中的字符串类，用来表示和操作字符串。

可以把它理解为：

对字符序列的封装
支持动态扩容
支持按下标访问
提供了常用的字符串处理接口

它本质上不是 C 风格字符串，但在很多场景下可以方便地和字符数组思维对应起来理解。

2）常用方法

string s = "hello";

s.size();          // 返回字符串长度
s.length();        // 与 size() 基本等价

s.empty();         // 判断是否为空

s[0];              // 按下标访问，不检查越界
s.at(0);           // 按下标访问，会检查越界

s.front();         // 访问首字符
s.back();          // 访问尾字符

s += "abc";        // 在末尾拼接字符串
s += 'x';          // 在末尾拼接字符
s.push_back('x');  // 在末尾添加一个字符
s.pop_back();      // 删除末尾字符

s.substr(pos, len);    // 从 pos 开始截取长度为 len 的子串
s.find("ab");          // 查找子串第一次出现的位置
s.find('a');           // 查找字符第一次出现的位置

s.erase(pos, len);     // 删除从 pos 开始、长度为 len 的一段
s.insert(pos, "abc");  // 在 pos 位置插入字符串
s.insert(pos, 1, 'x'); // 在 pos 位置插入若干个字符

reverse(s.begin(), s.end()); // 反转字符串

sort(s.begin(), s.end());    // 对字符串中的字符排序

if (s1 == s2) {}       // 判断是否相等
if (s1 < s2) {}        // 按字典序比较大小

for (char c : s) {}    // 范围 for 遍历
for (int i = 0; i < s.size(); i++) {} // 下标遍历

3）时间复杂度

常见操作复杂度可按下面理解：

按下标访问：O(1)
size() / length()：O(1)
front() / back()：O(1)
push_back()：均摊 O(1)
pop_back()：O(1)
+=：通常与追加内容长度有关，近似 O(k)
substr(pos, len)：O(len)
find()：一般按线性查找理解，常记为 O(n)
erase(pos, len)：O(n)
insert(pos, str)：O(n)
reverse()：O(n)
sort()：O(n log n)

刷题时最需要记住的是：

访问快
尾部操作快
中间插删通常不便宜
find、substr 不是常数时间

4）适用场景

string 常见于以下题型：

字符串模拟
双指针处理字符串
回文串判断
子串问题
字符频次统计
栈相关字符串题
表达式处理

5）常见坑

`substr(pos, len)` 的第二个参数是长度，不是结束下标

很多人会误写成：

s.substr(l, r);

这里的 r 会被解释为截取长度，不是右端点。
如果你想截取区间 [l, r]，应该写成：

s.substr(l, r - l + 1);

`find()` 找不到时返回 `string::npos`

规范写法：

if (s.find("abc") != string::npos) {}

不要把它简单理解成普通的 -1，虽然很多实现下效果接近，但笔记里最好写标准形式。

`operator[]` 不检查越界

s[i];

如果 i 越界，行为是不安全的。
需要检查时可以用：

s.at(i);

字符和字符串不要混淆

'a'    // 字符
"abc"  // 字符串字面量

这个在比较、拼接、传参时很容易写错。

在循环中修改字符串时要小心下标变化

尤其是用 erase() 删除字符时，后面的元素会前移。
如果一边遍历一边删除，容易漏处理元素或者越界。

`size()` 返回的是无符号类型

像下面这种写法要谨慎：

for (int i = s.size() - 1; i >= 0; i--)

当字符串为空时，s.size() - 1 可能出问题。
倒序遍历时要特别注意边界。

2. `std::vector`

1）它是什么

std::vector 是 C++ 标准库中的动态数组。

可以把它理解为：

长度可变的顺序表
元素连续存储
支持按下标随机访问
在尾部插入和删除效率较高

2）底层实现

vector 的底层本质上是 连续内存空间上的动态数组。

它有几个关键特点：

元素在内存中连续存放
可以像普通数组一样通过下标访问
当当前容量不够时，会申请一块更大的新内存
然后把原来的元素拷贝或移动过去，再释放旧空间

因此，vector 里有两个重要概念：

size()：当前实际元素个数
capacity()：当前已经分配好的容量

这也是为什么：

随机访问很快
尾插通常很快
中间插入、删除通常较慢
扩容时可能有额外的拷贝或移动开销

3）常用方法

vector<int> v;

v.size();                     // 返回当前元素个数
v.empty();                    // 判断是否为空
v.capacity();                 // 返回当前容量
v.clear();                    // 清空元素，size 变为 0
v.resize(n);                  // 调整元素个数为 n
v.resize(n, x);               // 调整元素个数为 n，不足部分用 x 填充
v.reserve(n);                 // 预留至少 n 的容量，减少扩容次数

v[0];                         // 按下标访问，不检查越界
v.at(0);                      // 按下标访问，会检查越界
v.front();                    // 访问首元素
v.back();                     // 访问尾元素

v.push_back(x);               // 在末尾插入一个已有元素
v.emplace_back(args...);      // 在末尾原地构造元素
v.pop_back();                 // 删除末尾元素

v.begin();                    // 返回首元素迭代器
v.end();                      // 返回尾后迭代器

v.insert(v.begin() + pos, x); // 在指定位置插入一个元素
v.erase(v.begin() + pos);     // 删除指定位置元素
v.erase(v.begin() + l, v.begin() + r); // 删除区间 [l, r)

sort(v.begin(), v.end());     // 排序
reverse(v.begin(), v.end());  // 反转

for (int x : v) {}            // 范围 for 遍历
for (int i = 0; i < v.size(); i++) {} // 下标遍历

4）时间复杂度

常见操作复杂度大致如下：

按下标访问：O(1)
front() / back()：O(1)
size()：O(1)
push_back() / emplace_back()：均摊 O(1)
pop_back()：O(1)
clear()：O(n)
insert() 在末尾以外位置插入：O(n)
erase() 删除中间元素：O(n)
resize()：通常按 O(n) 理解
sort()：O(n log n)
reverse()：O(n)

刷题时最重要的是记住：

随机访问快
尾插尾删快
中间插删慢
扩容会带来额外拷贝或移动开销

5）适用场景

一般来说，只要题目本质上是在处理“一段线性序列”，优先就可以考虑 vector。

6）常见坑

`vector` 扩容后，原有迭代器、指针、引用可能失效

这是很重要的一点。

因为扩容时可能会重新申请一块新内存，原来的地址就不再有效了。

`erase()` 删除元素后，后面的元素会前移

例如删除中间某个位置后：

后面的元素下标都会变化
相关迭代器也可能失效

所以在循环里删除元素时要特别小心。

`insert()` 和 `erase()` 都可能是线性复杂度

很多人刚开始会下意识觉得容器操作都很快，但 vector 的中间插删通常需要搬移元素，不是 O(1)。

`clear()` 清空的是元素，不一定释放容量

clear() 后：

size() 变成 0
但 capacity() 往往还在

这对复用容器有时是好事，但要知道它不是“彻底释放内存”。

`reserve()` 只改容量，不改元素个数

例如：

vector<int> v;
v.reserve(10);

这时：

可以预留空间
但 v.size() 仍然是 0
不能直接访问 v[0]

很多人会把 reserve() 和 resize() 搞混。

`resize()` 会真的改变元素个数

例如：

vector<int> v;
v.resize(10);

这时 v.size() 就变成 10 了，新增元素会被默认初始化。

`operator[]` 不检查越界

v[i];

如果下标越界，行为是不安全的。

需要检查时可以使用：

v.at(i);

倒序遍历时要注意 `size()` 是无符号类型

像下面这种写法要小心：

for (int i = v.size() - 1; i >= 0; i--)

当 v 为空时，v.size() - 1 可能出问题。
写倒序循环时要特别注意边界。

3. `std::deque`

1）它是什么

std::deque 是 C++ 标准库中的双端队列。

可以把它理解为：

支持头部和尾部高效插入、删除的线性容器
支持按下标访问元素
使用方式上有点像“既能当数组，又能当队列”

和 vector 相比，deque 最大的特点是：

不仅尾部操作快
头部操作也快

所以它很适合需要频繁在两端操作元素的题目。

2）底层实现

deque 的底层不是一整块完全连续的大数组。

它通常可以理解为：

一段“分段连续”的存储结构
外层有一个控制结构
内部由多个固定大小的连续缓冲区组成

也就是说：

每一小块内部通常是连续的
但整体不一定像 vector 那样放在一整块连续内存里

这也是为什么：

deque 支持随机访问
头尾插入删除效率高
但在内存布局上不如 vector 简单直接

3）常用方法

deque<int> dq;

dq.size();                           // 返回当前元素个数
dq.empty();                          // 判断是否为空
dq.clear();                          // 清空所有元素

dq[0];                               // 按下标访问，不检查越界
dq.at(0);                            // 按下标访问，会检查越界
dq.front();                          // 访问首元素
dq.back();                           // 访问尾元素

dq.push_back(x);                     // 在尾部插入一个已有元素
dq.emplace_back(args...);            // 在尾部原地构造元素
dq.push_front(x);                    // 在头部插入一个已有元素
dq.emplace_front(args...);           // 在头部原地构造元素
dq.pop_back();                       // 删除尾部元素
dq.pop_front();                      // 删除头部元素

dq.begin();                          // 返回首元素迭代器
dq.end();                            // 返回尾后迭代器

dq.insert(dq.begin() + pos, x);      // 在指定位置插入一个元素
dq.erase(dq.begin() + pos);          // 删除指定位置元素
dq.erase(dq.begin() + l, dq.begin() + r); // 删除区间 [l, r)

sort(dq.begin(), dq.end());          // 排序
reverse(dq.begin(), dq.end());       // 反转

for (int x : dq) {}                  // 范围 for 遍历
for (int i = 0; i < dq.size(); i++) {} // 下标遍历

4）时间复杂度

常见操作复杂度大致如下：

按下标访问：O(1)
front() / back()：O(1)
size()：O(1)
push_front() / emplace_front()：O(1)
push_back() / emplace_back()：O(1)
pop_front()：O(1)
pop_back()：O(1)
中间位置 insert()：O(n)
中间位置 erase()：O(n)
sort()：O(n log n)
reverse()：O(n)

刷题时最重要的是记住：

支持随机访问
头尾插删都快
中间插删仍然不便宜

5）适用场景

deque 常见于以下题型：

双端队列模拟
单调队列
滑动窗口最大值 / 最小值
需要同时维护头尾操作的场景
BFS 中某些需要特殊队列操作的题

deque 最典型的用途就是：

在头尾两端高效弹出和插入元素
维护滑动窗口中的单调性

6）常见坑

`deque` 虽然支持随机访问，但底层不是普通连续数组

所以不要把它完全等同于 vector。

它可以像数组一样 dq[i] 访问元素，但整体内存布局和 vector 不一样。

`deque` 的中间插入和删除仍然是线性复杂度

很多人会因为它头尾操作快，就误以为所有插删都快。

其实：

头部快
尾部快
中间并不快

`operator[]` 不检查越界

dq[i];

如果下标越界，行为是不安全的。

需要检查时可以使用：

dq.at(i);

在循环中删除元素时要注意迭代器失效

尤其是使用 erase() 删除中间元素时，相关迭代器可能失效。

如果一边遍历一边删，要格外小心。

`deque` 不要和 `queue` 混淆

deque 是容器
queue 是容器适配器

也就是说：

你可以直接遍历 deque
可以随机访问 deque
但 queue 不提供这些能力

不是所有需要“队列”的题都必须手写 `deque`

如果题目只需要普通先进先出：

优先考虑 queue

如果题目需要：

头尾都操作
单调队列
手动维护窗口

这时再考虑 deque 更合适。

4. `std::list`

1）它是什么

std::list 是 C++ 标准库中的双向链表。

可以把它理解为：

由一个个节点组成的线性容器
每个节点除了存数据，还会保存前驱和后继信息
支持在任意已知位置高效插入和删除
不支持按下标随机访问

和 vector、deque 相比，list 最大的特点是：

中间位置插入、删除方便
但访问某个位置不快

2）底层实现

list 的底层是 双向链表。

它的每个节点通常包含：

当前元素的值
指向前一个节点的指针
指向后一个节点的指针

这意味着：

节点在内存中通常不是连续存放的
不能像数组那样通过下标直接跳到第 i 个元素
但如果已经拿到了某个位置的迭代器，那么在这个位置附近做插入、删除会很方便

这也是为什么：

list 不支持随机访问
中间插删效率高
查找效率不高

3）常用方法

list<int> lst;

lst.size();                      // 返回当前元素个数
lst.empty();                     // 判断是否为空
lst.clear();                     // 清空所有元素

lst.front();                     // 访问首元素
lst.back();                      // 访问尾元素

lst.push_back(x);                // 在尾部插入一个已有元素
lst.emplace_back(args...);       // 在尾部原地构造元素
lst.push_front(x);               // 在头部插入一个已有元素
lst.emplace_front(args...);      // 在头部原地构造元素
lst.pop_back();                  // 删除尾部元素
lst.pop_front();                 // 删除头部元素

lst.begin();                     // 返回首元素迭代器
lst.end();                       // 返回尾后迭代器

auto it = lst.begin();
lst.insert(it, x);               // 在迭代器 it 指向的位置前插入元素
lst.emplace(it, args...);        // 在迭代器 it 指向的位置前原地构造元素
lst.erase(it);                   // 删除迭代器 it 指向的元素

lst.remove(x);                   // 删除所有值等于 x 的元素
lst.reverse();                   // 反转链表
lst.sort();                      // 对链表排序
lst.unique();                    // 删除连续重复元素

for (int x : lst) {}             // 范围 for 遍历
for (auto it = lst.begin(); it != lst.end(); ++it) {} // 迭代器遍历

4）时间复杂度

常见操作复杂度大致如下：

front() / back()：O(1)
size() / empty()：O(1)
push_front() / emplace_front()：O(1)
push_back() / emplace_back()：O(1)
pop_front() / pop_back()：O(1)
insert() / emplace()：已知位置时 O(1)
erase()：已知位置时 O(1)
按位置访问第 i 个元素：O(n)
查找某个值：O(n)
remove(x)：O(n)
reverse()：O(n)
sort()：O(n log n)
unique()：O(n)

刷题时最重要的是记住：

头尾操作快
已知位置插删快
查找慢
不支持随机访问

5）适用场景

list 常见于以下场景：

需要频繁在中间位置插入、删除元素
已经拿到了某个位置的迭代器，再在该位置附近修改结构
题目本质更偏向链表操作，而不是数组操作
某些需要维护顺序且频繁删除节点的模拟题

很多时候：

如果只需要线性存储，优先考虑 vector
如果需要头尾高效操作，优先考虑 deque
只有明确需要链表特性时，再考虑 list

6）常见坑

`list` 不支持按下标随机访问

不能写：

lst[0];

也不能做：

lst.begin() + 3;

因为 list 的迭代器不是随机访问迭代器，只能一步一步移动。

查找慢，不要因为插删快就误以为它整体都快

list 的优势是：

已知位置插删快

但如果你连这个位置都要先找半天，那查找本身仍然是 O(n)。

`sort()` 不能写成通用算法的 `sort(lst.begin(), lst.end())`

对于 list，通常要写：

lst.sort();

而不是：

sort(lst.begin(), lst.end());

因为标准库的 sort 需要随机访问迭代器，而 list 不提供。

`unique()` 只会删除连续重复元素

例如：

list<int> lst = {1, 1, 2, 2, 3};
lst.unique();

这样可以去掉相邻重复。

但如果重复元素不是连续的，unique() 不会帮你全局去重。

`remove(x)` 和算法里的 `remove` 不是一回事

list 有自己的成员函数：

lst.remove(x);

它会真正删除值为 x 的节点。

而泛型算法里的 remove 只是“逻辑挪动”，这两个不要混淆。

`list` 的内存开销通常比 `vector` 更大

因为每个节点除了存值，还要额外存前驱、后继指针。

所以：

空间利用率不如 vector
缓存局部性也通常更差

5. `std::set` / `std::multiset`

1）它们是什么

std::set 和 std::multiset 都是 C++ 标准库中的有序关联容器。

可以把它们理解为：

内部元素会自动按升序排列
插入后不需要手动排序
查找、插入、删除效率都比较稳定

它们的区别主要在于：

set：元素唯一，不允许重复
multiset：元素可重复，允许多个相同值同时存在

例如：

set<int> s = {1, 2, 2, 3}; 里最终只有 1, 2, 3
multiset<int> ms = {1, 2, 2, 3}; 里会保留两个 2

2）底层实现

set 和 multiset 的底层通常是 红黑树，属于一种自平衡二叉搜索树。

这意味着：

元素始终保持有序
查找、插入、删除的时间复杂度通常都是 O(log n)
不支持像数组那样按下标随机访问
可以方便地做“找第一个大于等于 x 的元素”这类有序查询

这也是为什么它们很适合处理：

有序去重
动态维护有序集合
前驱 / 后继查找
区间边界问题

3）常用方法

set<int> s;
multiset<int> ms;

s.size();                      // 返回当前元素个数
s.empty();                     // 判断是否为空
s.clear();                     // 清空所有元素

s.insert(x);                   // 插入元素
s.emplace(x);                  // 原地构造元素
s.erase(x);                    // 删除值为 x 的元素
s.find(x);                     // 查找值为 x 的元素，找不到返回 end()
s.count(x);                    // 统计 x 的个数，set 中结果只可能是 0 或 1
s.contains(x);                 // 判断是否包含 x（C++20）
s.lower_bound(x);              // 返回第一个 >= x 的迭代器
s.upper_bound(x);              // 返回第一个 > x 的迭代器
s.begin();                     // 返回首元素迭代器
s.end();                       // 返回尾后迭代器
s.rbegin();                    // 返回逆序首元素迭代器
s.rend();                      // 返回逆序尾后迭代器

ms.size();                     // 返回当前元素个数
ms.empty();                    // 判断是否为空
ms.clear();                    // 清空所有元素

ms.insert(x);                  // 插入元素
ms.emplace(x);                 // 原地构造元素
ms.erase(x);                   // 删除所有值为 x 的元素
ms.find(x);                    // 查找一个值为 x 的元素
ms.count(x);                   // 统计 x 的个数
ms.contains(x);                // 判断是否包含 x（C++20）
ms.lower_bound(x);             // 返回第一个 >= x 的迭代器
ms.upper_bound(x);             // 返回第一个 > x 的迭代器
ms.begin();                    // 返回首元素迭代器
ms.end();                      // 返回尾后迭代器
ms.rbegin();                   // 返回逆序首元素迭代器
ms.rend();                     // 返回逆序尾后迭代器

auto it = s.find(x);
if (it != s.end()) s.erase(it);    // 按迭代器删除一个元素

auto range = ms.equal_range(x);    // 返回所有等于 x 的区间 [lower_bound, upper_bound)

for (int x : s) {}                 // 范围 for 遍历
for (auto it = s.begin(); it != s.end(); ++it) {} // 迭代器遍历

4）时间复杂度

常见操作复杂度大致如下：

size() / empty()：O(1)
insert() / emplace()：O(log n)
erase()：O(log n) 或 O(log n + k)
find() / count() / contains()：O(log n)
lower_bound() / upper_bound()：O(log n)
begin() / end()：O(1)

其中：

对 set 来说，count(x) 结果只会是 0 或 1
对 multiset 来说，erase(x) 删除所有值为 x 的元素，若有 k 个，通常可理解为 O(log n + k)

刷题时最重要的是记住：

自动有序
查找、插入、删除都比较稳定
不支持随机访问
比 unordered_set 慢一些，但更适合处理有序问题

5）适用场景

set / multiset 常见于以下题型：

需要自动排序
需要动态维护一个有序集合
查找前驱 / 后继
查找第一个大于等于某值的元素
维护窗口中的最值或中位数
需要处理重复元素且保持有序
扫描线、区间边界、贪心中的有序选择

一般来说：

只需要去重且不关心顺序，优先考虑 unordered_set
需要有序，考虑 set
需要有序且允许重复，考虑 multiset

6）常见坑

`set` 和 `multiset` 不支持下标访问

不能写：

s[0];
ms[0];

它们不是数组，也不是 vector，不能按位置直接取第几个元素。

它们的迭代器不是随机访问迭代器

不能写：

s.begin() + 1;

如果想移动迭代器，只能用 ++it，或者使用 next(it)、prev(it)。

`set` 不允许重复，`multiset` 允许重复

这个最基础，但做题时很容易因为题意没看清而选错容器。

如果题目里可能出现多个相同值，而且这些相同值都要保留，就不能用 set。

`multiset.erase(x)` 会删掉所有值等于 `x` 的元素

例如：

multiset<int> ms = {1, 2, 2, 2, 3};
ms.erase(2);

这样会把所有的 2 都删掉。

如果你只想删一个 2，应该先找迭代器，再按迭代器删除：

auto it = ms.find(2);
if (it != ms.end()) ms.erase(it);

`set.erase(x)` 和 `set.erase(it)` 的含义不同

erase(x)：按值删除
erase(it)：按迭代器删除

对 multiset 来说，这个区别尤其重要，因为按值删可能删掉一整批重复元素。

`count()` 在 `set` 里不是“统计很多个”

因为 set 不允许重复，所以：

s.count(x) 只可能是 0 或 1

如果你只是想判断某元素是否存在，find() 或 contains() 往往更直接。

`lower_bound()` 和 `upper_bound()` 容易记混

lower_bound(x)：第一个 大于等于 x 的位置
upper_bound(x)：第一个大于 x 的位置

这是 set / multiset 的高频考点。

`unordered_set` 更快，但不能替代所有 `set`

很多人会觉得哈希表平均 O(1)，所以总比 set 好。

但只要题目涉及：

有序
前驱后继
范围查询
lower_bound / upper_bound

这些都更适合 set / multiset。

想取最大值、最小值时不要忘了迭代器写法

例如：

*s.begin();        // 最小值
*prev(s.end());    // 最大值

对 multiset 也一样适用。

但要注意容器不能为空，否则解引用会出问题。

6. `std::map` / `std::multimap`

1）它们是什么

std::map 和 std::multimap 都是 C++ 标准库中的有序关联容器，用来存储键值对，也就是 key-value 结构。

可以把它们理解为：

内部元素会按照 key 自动升序排列
每个元素本质上是一个键值对
支持根据 key 查找、插入、删除
适合处理“键到值的映射关系”

它们的区别主要在于：

map：key 唯一，同一个 key 只能出现一次
multimap：key 可重复，同一个 key 可以出现多次

例如：

map<int, string> 适合记录“学号 -> 姓名”
multimap<int, string> 适合记录“分数 -> 多个姓名”

2）底层实现

map 和 multimap 的底层通常是 红黑树，属于自平衡二叉搜索树。

这意味着：

元素始终按 key 有序
查找、插入、删除的时间复杂度通常都是 O(log n)
不支持像数组那样按下标随机访问
可以方便地做有序查询，比如找第一个 key >= x 的元素

这也是为什么它们很适合处理：

有序映射
前驱 / 后继问题
区间边界问题
需要按 key 自动排序的场景

3）常用方法

map<int, string> mp;
multimap<int, string> mmp;

mp.size();                         // 返回当前元素个数
mp.empty();                        // 判断是否为空
mp.clear();                        // 清空所有元素

mp[key];                           // 访问 key 对应的 value，若 key 不存在会插入默认值
mp.at(key);                        // 访问 key 对应的 value，若 key 不存在会抛异常
mp.insert({key, value});           // 插入键值对
mp.emplace(key, value);            // 原地构造键值对
mp.erase(key);                     // 删除 key 对应的元素
mp.find(key);                      // 查找 key，找不到返回 end()
mp.count(key);                     // 统计 key 的个数，map 中结果只可能是 0 或 1
mp.contains(key);                  // 判断是否包含 key（C++20）
mp.lower_bound(key);               // 返回第一个 key >= 给定值的迭代器
mp.upper_bound(key);               // 返回第一个 key > 给定值的迭代器
mp.begin();                        // 返回首元素迭代器
mp.end();                          // 返回尾后迭代器
mp.rbegin();                       // 返回逆序首元素迭代器
mp.rend();                         // 返回逆序尾后迭代器

mmp.size();                        // 返回当前元素个数
mmp.empty();                       // 判断是否为空
mmp.clear();                       // 清空所有元素

mmp.insert({key, value});          // 插入键值对
mmp.emplace(key, value);           // 原地构造键值对
mmp.erase(key);                    // 删除所有 key 等于给定值的元素
mmp.find(key);                     // 查找一个 key 等于给定值的元素
mmp.count(key);                    // 统计 key 的个数
mmp.contains(key);                 // 判断是否包含 key（C++20）
mmp.lower_bound(key);              // 返回第一个 key >= 给定值的迭代器
mmp.upper_bound(key);              // 返回第一个 key > 给定值的迭代器
mmp.begin();                       // 返回首元素迭代器
mmp.end();                         // 返回尾后迭代器
mmp.rbegin();                      // 返回逆序首元素迭代器
mmp.rend();                        // 返回逆序尾后迭代器

auto it1 = mp.find(key);
if (it1 != mp.end()) mp.erase(it1);    // 按迭代器删除一个元素

auto it2 = mmp.find(key);
if (it2 != mmp.end()) mmp.erase(it2);  // 只删除一个 key 对应的元素

auto range = mmp.equal_range(key);     // 返回所有 key 等于给定值的区间 [lower_bound, upper_bound)

for (auto &[k, v] : mp) {}             // 范围 for 遍历
for (auto it = mp.begin(); it != mp.end(); ++it) {} // 迭代器遍历

4）时间复杂度

常见操作复杂度大致如下：

size() / empty()：O(1)
insert() / emplace()：O(log n)
erase()：O(log n) 或 O(log n + k)
find() / count() / contains()：O(log n)
lower_bound() / upper_bound()：O(log n)
mp[key] / mp.at(key)：O(log n)
begin() / end()：O(1)

其中：

对 map 来说，count(key) 结果只会是 0 或 1
对 multimap 来说，erase(key) 会删除所有对应 key 的元素，若有 k 个，通常可理解为 O(log n + k)

刷题时最重要的是记住：

自动按 key 有序
查找、插入、删除复杂度稳定
不支持随机访问
比 unordered_map 慢一些，但更适合处理有序问题

5）适用场景

map / multimap 常见于以下题型：

需要维护“key -> value”的映射关系
需要 key 自动排序
需要查找前驱 / 后继
需要找第一个 key >= x 的位置
扫描线、区间边界、事件排序
统计信息同时保持 key 有序
一个 key 需要对应多个 value 的有序场景

一般来说：

只需要快速映射，不关心顺序，优先考虑 unordered_map
需要按 key 有序，考虑 map
需要按 key 有序且允许重复 key，考虑 multimap

6）常见坑

`map` 和 `multimap` 不支持下标随机访问

不能写：

mp[0][1];
mmp[0][1];

它们不是数组，也不是 vector，不能按“第几个元素”直接访问。

`map[key]` 会在 key 不存在时插入默认值

例如：

map<int, int> mp;
cout << mp[10];

这不仅会访问，还会插入一个 {10, 0}。

所以如果你只是想判断某个 key 是否存在，优先考虑：

mp.find(key);
mp.contains(key);

`multimap` 没有 `operator[]`

不能写：

mmp[key];

因为 multimap 允许同一个 key 对应多个 value，[] 这种“一对一访问”语义不成立。

`map::insert()` 遇到重复 key 时不会覆盖旧值

例如：

map<int, int> mp;
mp.insert({1, 10});
mp.insert({1, 20});

第二次插入不会把 10 改成 20。

如果你想覆盖原值，通常写：

mp[1] = 20;

`multimap.erase(key)` 会删掉所有该 key 的元素

例如：

multimap<int, string> mmp;
mmp.emplace(1, "a");
mmp.emplace(1, "b");
mmp.erase(1);

这样会把 key 为 1 的所有键值对都删掉。

如果你只想删一个，应该先拿迭代器，再按迭代器删除。

`lower_bound()` 和 `upper_bound()` 容易记混

lower_bound(key)：第一个 key >= 给定值 的位置
upper_bound(key)：第一个 key > 给定值 的位置

这是 map / multimap 的高频考点。

遍历 `map` 时拿到的是键值对，不是单个值

例如：

for (auto &[k, v] : mp) {}

这里每个元素都是一组 (key, value)，不是只有一个整数或字符串。

`unordered_map` 更快，但不能替代所有 `map`

很多人会觉得哈希表平均 O(1)，所以总比 map 好。

但只要题目涉及：

key 有序
前驱后继
范围查询
lower_bound() / upper_bound()

这些都更适合 map / multimap。

`map` 中 key 默认按升序排列，不是按插入顺序

这一点很容易被忽略。

例如你按顺序插入：

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

遍历时顺序仍然是：

而不是插入顺序。

7. `std::unordered_set`

1）它是什么

std::unordered_set 是 C++ 标准库中的无序关联容器，用来存储一组不重复的元素。

可以把它理解为：

元素唯一
内部不按大小排序
更关注“能不能快速找到某个值”
适合做快速判重和快速查询

和 set 相比，unordered_set 最大的特点是：

不保证有序
平均查找更快

所以如果题目只关心“某个元素在不在”，而不关心顺序，通常会优先考虑 unordered_set。

2）底层实现

unordered_set 的底层通常是 哈希表。

你可以把它理解为：

先通过哈希函数把元素映射到某个桶（bucket）
再在对应桶里存储这个元素

这意味着：

元素整体是无序的
平均情况下查找、插入、删除都比较快
但如果哈希冲突严重，性能可能退化

这也是为什么：

unordered_set 很适合快速查重
但不适合处理有序相关问题
也不支持 lower_bound()、upper_bound() 这类有序操作

3）常用方法

unordered_set<int> us;

us.size();                      // 返回当前元素个数
us.empty();                     // 判断是否为空
us.clear();                     // 清空所有元素

us.insert(x);                   // 插入元素
us.emplace(x);                  // 原地构造元素
us.erase(x);                    // 删除值为 x 的元素
us.find(x);                     // 查找值为 x 的元素，找不到返回 end()
us.count(x);                    // 判断 x 是否存在，结果只可能是 0 或 1
us.contains(x);                 // 判断是否包含 x（C++20）

us.begin();                     // 返回首元素迭代器
us.end();                       // 返回尾后迭代器

us.bucket_count();              // 返回桶的数量
us.bucket(x);                   // 返回元素 x 所在的桶编号
us.load_factor();               // 返回当前负载因子
us.rehash(n);                   // 重新分配桶的数量
us.reserve(n);                  // 预留空间，减少 rehash 次数

auto it = us.find(x);
if (it != us.end()) us.erase(it); // 按迭代器删除元素

for (int x : us) {}             // 范围 for 遍历
for (auto it = us.begin(); it != us.end(); ++it) {} // 迭代器遍历

4）时间复杂度

常见操作复杂度大致如下：

size() / empty()：O(1)
insert() / emplace()：平均 O(1)，最坏 O(n)
erase()：平均 O(1)，最坏 O(n)
find() / count() / contains()：平均 O(1)，最坏 O(n)
clear()：O(n)
rehash() / reserve()：通常按 O(n) 理解
begin() / end()：O(1)

刷题时最重要的是记住：

平均查找很快
不保证顺序
最坏情况下可能退化
不能做有序查询

5）适用场景

unordered_set 常见于以下题型：

快速判重
判断某个值是否存在
数组去重
哈希查找
图或搜索中的访问标记
滑动窗口中的元素存在性判断
需要快速插入、删除、查询，但不要求顺序的题

一般来说：

只关心“在不在”，优先考虑 unordered_set
需要自动有序，考虑 set

6）常见坑

`unordered_set` 是无序的

遍历顺序不表示大小顺序，也不表示插入顺序。

例如：

unordered_set<int> us = {3, 1, 2};

遍历出来的顺序不一定是：

1 2 3

也不一定是：

3 1 2

所以不要对遍历顺序有任何依赖。

它不支持 `lower_bound()`、`upper_bound()` 这类有序操作

因为它不是有序容器，所以不能像 set 一样做：

找第一个大于等于某个值的元素
找前驱 / 后继
做范围查询

如果题目需要这些能力，应该考虑 set。

`count()` 的结果只可能是 `0` 或 `1`

因为 unordered_set 不允许重复元素，所以：

us.count(x) 只可能返回 0 或 1

它本质上更像“是否存在”的判断，而不是真正统计很多个。

自定义类型不能直接用，通常要自定义哈希函数

例如如果你想写：

unordered_set<pair<int, int>> us;

很多环境下不能直接通过编译，需要自己提供哈希函数。

尤其是想把：

pair
自定义结构体
自定义类

放进 unordered_set 的时候。

`erase(x)` 和 `erase(it)` 含义不同

erase(x)：按值删除
erase(it)：按迭代器删除

虽然 unordered_set 里一个值最多只有一个，但写法上还是要分清楚。

rehash 之后迭代器可能失效

当哈希表扩容、桶重分配时，原有迭代器可能失效。

所以如果你一边遍历一边插入很多元素，要注意这一点。

平均 `O(1)` 不等于绝对比 `set` 更好

很多人会下意识觉得：

unordered_set 平均 O(1)
set 是 O(log n)
所以前者一定更强

但如果题目需要：

有序
前驱 / 后继
范围查询
稳定的树结构语义

这些情况下 set 更合适。

`reserve()` 和 `rehash()` 是优化，不是必须会用

刷题时大多数情况下不用手动调它们。

但知道它们的作用会更好：

reserve(n)：预留空间，减少扩容次数
rehash(n)：调整桶数量

当你插入大量元素时，它们可能有助于减少 rehash 开销。

8. `std::unordered_map`

1）它是什么

std::unordered_map 是 C++ 标准库中的无序关联容器，用来存储键值对，也就是 key-value 结构。

可以把它理解为：

通过 key 快速找到对应的 value
内部元素不按 key 排序
更关注“查得快”，而不是“有序”
非常适合做计数、映射、查找

和 map 相比，unordered_map 最大的特点是：

不保证有序
平均查找、插入、删除更快

所以如果题目只关心：

某个 key 是否存在
某个 key 对应什么 value
某个 key 出现了多少次

通常都会优先考虑 unordered_map。

2）底层实现

unordered_map 的底层通常是 哈希表。

你可以把它理解为：

先通过哈希函数把 key 映射到某个桶（bucket）
再在对应桶里存储这个键值对

这意味着：

元素整体是无序的
平均情况下查找、插入、删除都比较快
但如果哈希冲突严重，性能可能退化

这也是为什么：

unordered_map 很适合快速映射和频次统计
但不适合处理有序相关问题
也不支持 lower_bound()、upper_bound() 这类有序操作

3）常用方法

unordered_map<int, int> mp;

mp.size();                       // 返回当前元素个数
mp.empty();                      // 判断是否为空
mp.clear();                      // 清空所有元素

mp[key];                         // 访问 key 对应的 value，若 key 不存在会插入默认值
mp.at(key);                      // 访问 key 对应的 value，若 key 不存在会抛异常
mp.insert({key, value});         // 插入键值对
mp.emplace(key, value);          // 原地构造键值对
mp.erase(key);                   // 删除 key 对应的元素
mp.find(key);                    // 查找 key，找不到返回 end()
mp.count(key);                   // 判断 key 是否存在，结果只可能是 0 或 1
mp.contains(key);                // 判断是否包含 key（C++20）

mp.begin();                      // 返回首元素迭代器
mp.end();                        // 返回尾后迭代器

mp.bucket_count();               // 返回桶的数量
mp.bucket(key);                  // 返回 key 所在的桶编号
mp.load_factor();                // 返回当前负载因子
mp.rehash(n);                    // 重新分配桶的数量
mp.reserve(n);                   // 预留空间，减少 rehash 次数

auto it = mp.find(key);
if (it != mp.end()) mp.erase(it); // 按迭代器删除元素

for (auto &[k, v] : mp) {}       // 范围 for 遍历
for (auto it = mp.begin(); it != mp.end(); ++it) {} // 迭代器遍历

4）时间复杂度

常见操作复杂度大致如下：

size() / empty()：O(1)
insert() / emplace()：平均 O(1)，最坏 O(n)
erase()：平均 O(1)，最坏 O(n)
find() / count() / contains()：平均 O(1)，最坏 O(n)
mp[key] / mp.at(key)：平均 O(1)，最坏 O(n)
clear()：O(n)
rehash() / reserve()：通常按 O(n) 理解
begin() / end()：O(1)

刷题时最重要的是记住：

平均查找很快
不保证顺序
最坏情况下可能退化
不能做有序查询

5）适用场景

unordered_map 常见于以下题型：

频次统计
两数之和
前缀和计数
key 到 value 的快速映射
字符统计
哈希查找
滑动窗口中的计数维护
图、树、搜索中的状态映射

一般来说：

只关心快速映射，不关心顺序，优先考虑 unordered_map
需要 key 自动有序，考虑 map

6）常见坑

`unordered_map` 是无序的

遍历顺序不表示 key 的大小顺序，也不表示插入顺序。

例如：

unordered_map<int, int> mp;
mp[3] = 30;
mp[1] = 10;
mp[2] = 20;

遍历出来的顺序不一定是：

1 2 3

也不一定是插入顺序。

所以不要依赖它的遍历顺序。

`mp[key]` 在 key 不存在时会插入默认值

这是 unordered_map 最重要的坑之一。

例如：

unordered_map<int, int> mp;
cout << mp[10];

这不仅会访问，还会插入一个：

key = 10
value = 0

如果 value 类型是 string，那就会插入空字符串；如果是 vector<int>，那就会插入一个空 vector。

所以如果你只是想判断某个 key 是否存在，优先考虑：

mp.find(key);
mp.contains(key);

`count()` 的结果只可能是 `0` 或 `1`

因为 unordered_map 的 key 不允许重复，所以：

mp.count(key) 只可能返回 0 或 1

它本质上更像“是否存在”的判断，而不是真正统计很多个。

`at()` 和 `operator[]` 的行为不同

mp[key]：key 不存在时会插入默认值
mp.at(key)：key 不存在时会抛异常

刷题里最常用的是 mp[key]，但要清楚它有副作用。

自定义类型做 key 时，通常要自定义哈希函数

例如如果你想写：

unordered_map<pair<int, int>, int> mp;

很多环境下不能直接通过编译，需要自己提供哈希函数。

尤其是想把：

pair
自定义结构体
自定义类

作为 key 的时候。

rehash 之后迭代器可能失效

当哈希表扩容、桶重分配时，原有迭代器可能失效。

所以如果你一边遍历一边插入很多元素，要注意这一点。

平均 `O(1)` 不等于一定比 `map` 更好

很多人会下意识觉得：

unordered_map 平均 O(1)
map 是 O(log n)
所以前者一定更强

但如果题目需要：

key 有序
前驱 / 后继
范围查询
lower_bound() / upper_bound()

这些情况下 map 更合适。

`reserve()` 和 `rehash()` 是优化，不是必须会用

刷题时大多数情况下不用手动调它们。

但知道它们的作用会更好：

reserve(n)：预留空间，减少扩容次数
rehash(n)：调整桶数量

当你要插入大量元素时，它们可能有助于减少 rehash 开销。

9. `std::stack`

1）它是什么

std::stack 是 C++ 标准库中的栈，也就是一种 后进先出（LIFO，Last In First Out）的容器适配器。

可以把它理解为：

只能在一端进行插入和删除
最后放进去的元素会最先取出来
适合处理“最近加入的元素优先处理”的问题

它不是一个完整的顺序容器，而是对底层容器的一层封装。
使用时通常只关心：

入栈
出栈
取栈顶元素
判空

2）底层实现

stack 本质上是 容器适配器，不是独立的数据结构容器。

它默认基于 deque 实现，也可以基于：

vector
list

来实现。

不过默认情况下你通常直接写：

stack<int> st;

就可以了，底层会默认使用 deque。

它的特点是：

不支持遍历
不支持随机访问
不提供迭代器
只允许访问栈顶元素

这也是为什么 stack 更像是“对某种受限操作场景的封装”。

3）常用方法

stack<int> st;

st.size();              // 返回当前元素个数
st.empty();             // 判断是否为空

st.push(x);             // 将已有元素压入栈顶
st.emplace(args...);    // 在栈顶原地构造元素
st.pop();               // 删除栈顶元素
st.top();               // 访问栈顶元素

stack<int> st2;
st.swap(st2);           // 与另一个 stack 交换内容

4）适用场景

stack 常见于以下题型：

括号匹配
表达式求值
去除相邻重复字符
单调栈
模拟递归过程
DFS 的非递归写法
需要“后进先出”处理顺序的问题

在 LeetCode 中，stack 最典型的用途包括：

有效括号
每日温度
柱状图最大矩形
字符串消除类问题
表达式与语法分析类问题

一般来说，只要题目特征是：

只关心最新加入的元素
需要频繁取“最近的那个”
匹配关系天然呈嵌套结构

就可以考虑 stack。

10. `std::queue`

1）它是什么

std::queue 是 C++ 标准库中的队列，也就是一种 先进先出（FIFO，First In First Out）的容器适配器。

可以把它理解为：

元素从队尾进入
元素从队头离开
先放进去的元素会先取出来
适合处理“按进入顺序依次处理”的问题

它不是一个完整的顺序容器，而是对底层容器的一层封装。
使用时通常只关心：

入队
出队
访问队头元素
访问队尾元素
判空

2）底层实现

queue 本质上是 容器适配器，不是独立的数据结构容器。

它默认基于 deque 实现，也可以基于：

list

来实现。

不过默认情况下你通常直接写：

queue<int> q;

就可以了，底层会默认使用 deque。

它的特点是：

不支持遍历
不支持随机访问
不提供迭代器
只能访问队头和队尾元素

这也是为什么 queue 更像是“对先进先出这种受限操作场景的封装”。

3）常用方法

queue<int> q;

q.size();              // 返回当前元素个数
q.empty();             // 判断是否为空

q.push(x);             // 将已有元素加入队尾
q.emplace(args...);    // 在队尾原地构造元素
q.pop();               // 删除队头元素
q.front();             // 访问队头元素
q.back();              // 访问队尾元素

queue<int> q2;
q.swap(q2);            // 与另一个 queue 交换内容

4）适用场景

queue 常见于以下题型：

BFS
二叉树层序遍历
图的广度优先搜索
最短步数问题
拓扑排序中的入度处理
模拟排队过程
按时间顺序或层级顺序处理状态的问题

在 LeetCode 中，queue 最典型的用途包括：

二叉树层序遍历
岛屿问题中的 BFS
最短路径的无权图搜索
拓扑排序
多源 BFS

一般来说，只要题目特征是：

先进入的状态要先处理
按层扩展
按步数一圈一圈向外扩展

就可以考虑 queue。

11. `std::priority_queue`

1）它是什么

std::priority_queue 是 C++ 标准库中的优先队列，也是一种容器适配器。

可以把它理解为：

不是按进入顺序取元素
而是每次优先取出“优先级最高”的元素
默认情况下，最大的元素会先出来

所以它和普通 queue 的区别在于：

queue：先进先出
priority_queue：优先级高的先出

常用来处理“动态维护当前最大值 / 最小值”的问题。

2）底层实现

priority_queue 本质上是 容器适配器，底层通常基于堆实现，默认是 大顶堆。

也就是说：

队首元素总是当前最大的元素
插入一个元素后，会自动调整堆结构
删除堆顶后，也会自动调整堆结构

默认情况下你通常直接写：

priority_queue<int> pq;

这时默认行为是：

top() 取到的是最大值

如果你想要小顶堆，可以写成：

priority_queue<int, vector<int>, greater<int>> pq;

这时：

top() 取到的是最小值

3）常用方法

priority_queue<int> pq;

pq.size();                         // 返回当前元素个数
pq.empty();                        // 判断是否为空

pq.push(x);                        // 将已有元素压入优先队列
pq.emplace(args...);               // 原地构造元素
pq.pop();                          // 删除堆顶元素
pq.top();                          // 访问堆顶元素

priority_queue<int> pq2;
pq.swap(pq2);                      // 与另一个 priority_queue 交换内容

priority_queue<int> maxpq;         // 默认大顶堆，堆顶是最大值
priority_queue<int, vector<int>, greater<int>> minpq; // 小顶堆，堆顶是最小值

4）时间复杂度

常见操作复杂度大致如下：

size() / empty()：O(1)
top()：O(1)
push() / emplace()：O(log n)
pop()：O(log n)
swap()：O(1)

刷题时最重要的是记住：

看堆顶快
插入和删除堆顶都比较快
适合动态维护最值
但不适合查找任意元素

5）适用场景

priority_queue 常见于以下题型：

Top K 问题
动态维护最大值 / 最小值
贪心中每次取当前最优
合并多个有序结构
Dijkstra 算法
数据流问题
反复取出当前最小或最大的元素进行处理

在 LeetCode 中，priority_queue 最典型的用途包括：

数组中的第 K 个最大元素
合并 K 个有序链表
前 K 个高频元素
数据流中的中位数
最短路径
会议室 / 任务调度类问题

一般来说，只要题目特征是：

每一步都要快速拿当前最优元素
元素会动态加入
不需要整体排序，只需要反复取堆顶

就可以考虑 priority_queue。

6）常见坑

`priority_queue` 默认是大顶堆

很多人第一次用会默认以为它是最小值先出。

实际上：

priority_queue<int> pq;

默认是大顶堆，也就是：

top() 返回最大值

如果你要小顶堆，通常写：

priority_queue<int, vector<int>, greater<int>> pq;

它不是普通队列，不是先进先出

priority_queue 取元素的顺序和插入顺序没有关系。

它只关心谁的优先级更高。

只能访问堆顶，不能遍历，也不能随机访问

和 stack、queue 一样，priority_queue 是容器适配器。

它不提供：

迭代器
下标访问
遍历接口

所以你不能像 vector 一样把里面所有元素直接扫一遍。

不能高效删除或查找任意一个中间元素

priority_queue 擅长的是：

插入元素
取堆顶
删除堆顶

但如果你想：

删除某个指定值
查找某个值是否存在
修改堆中某个中间元素

它并不适合。

`greater<int>` 写出来的是小顶堆，不要记反

这个地方很容易绕。

priority_queue<int, vector<int>, greater<int>> pq;

这样写时，堆顶是最小值。

因为比较器决定的是“谁更优先留在堆顶”。

存 `pair` 时，默认比较规则要清楚

例如：

priority_queue<pair<int, int>> pq;

默认会先比较 first，如果 first 相等，再比较 second。

所以如果题目要求的优先级规则比较特殊，往往要自己写比较器。

小顶堆写法容易长，面试和笔记里最好记住模板

最常用的小顶堆模板就是：

priority_queue<int, vector<int>, greater<int>> pq;

这个在 Top K、最短路、区间调度里都很常见。

`push()` 和 `emplace()` 复杂度同阶，但 `emplace()` 更适合原地构造对象

比如存 pair 时：

priority_queue<pair<int, int>> pq;
pq.push({1, 2});
pq.emplace(1, 2);

两者复杂度同阶，但 emplace() 是原地构造，写法也常常更自然。

12. 常用 STL 算法

1）排序：`sort`、`reverse`

2）二分：`lower_bound`、`upper_bound`、`binary_search`

3）去重：`unique`

4）统计：`count`、`accumulate`

5）最值：`max_element`、`min_element`

13. 迭代器与失效问题

1）什么是迭代器失效

2）`vector` 的失效规则

3）`list` 的失效规则

4）`map / set` 的失效规则

5）`unordered_map` 的失效规则

14. STL 高频对比

1）`map` 和 `unordered_map`

2）`set` 和 `unordered_set`

3）`vector` 和 `list`

4）`queue` 和 `priority_queue`

15. STL 常见坑速记

1）`unordered_map[key]` 会插入默认值

2）`priority_queue` 默认是大顶堆

3）`vector.erase()` 是线性复杂度

4）`set` 和 `map` 不能下标访问

5）`string::find()` 找不到返回 `npos`

二、二分查找

1. 二分查找的本质

1）有序区间上缩小答案范围

二分查找最核心的前提是：答案具有单调性。

最经典的情况是数组有序，例如：

左边一段都小于目标值
右边一段都大于等于目标值

这时候我们就可以通过比较中间位置 mid 和目标值的关系，判断：

答案在左边
还是在右边

也就是说，二分并不是“在中间找一下”，而是：

利用有序性或单调性，把不可能的那一半直接排除掉。

2）每次排除一半搜索空间

假设当前搜索区间是 [l, r]。

每次取中点 mid 之后，根据条件判断：

保留左半边
或保留右半边

于是区间长度会不断缩小，大致变成原来的一半。

所以二分查找的时间复杂度是：

O(log n)

这也是为什么：

顺序查找是 O(n)
二分查找快得多

3）关键在于边界更新是否正确

二分最容易错的地方，不是“会不会写”，而是：

边界怎么收缩
mid 应该偏左还是偏右
区间定义是闭区间还是半开区间
循环结束条件是什么

也就是说，二分的本质不是背模板，而是搞清楚：

当前保留的是哪一边，下一轮区间是否一定变小。

只要边界更新写错，就可能导致：

死循环
少查一个位置
左右边界错一位

2. 基础模板

1）查找某个具体值

这是最经典的二分查找，适用于：

已排序数组
查找某个值是否存在
如果存在，返回它的位置

int binarySearch(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

这个模板的特点是：

搜索区间是闭区间 [l, r]
while (l <= r)
找到就直接返回
否则继续去左边或右边找

如果最后没找到，就返回 -1。

2）查找左边界

左边界问题的本质是：

找第一个满足条件的位置。

比如：

第一个大于等于 target 的位置
第一个等于 target 的位置

常见模板如下：

int lowerBound(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;
}

这个模板的特点是：

搜索区间仍然是闭区间
while (l < r)
mid 偏左
如果当前位置已经满足条件，就保留左半边，包括 mid
否则去右边

最后 l == r 时，这个位置就是答案候选。

如果题目要求的是“第一个等于 target 的位置”，通常还要在最后判断一下这个位置是否合法。

3）查找右边界

右边界问题的本质是：

找最后一个满足条件的位置。

比如：

最后一个小于等于 target 的位置
最后一个等于 target 的位置

常见模板如下：

int upperBoundLeft(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + ((r - l + 1) >> 1);
        if (nums[mid] <= target) l = mid;
        else r = mid - 1;
    }
    return l;
}

这个模板的特点是：

while (l < r)
mid 偏右
如果当前位置满足条件，就保留右半边，包括 mid
否则去左边

最后 l == r 时，这个位置就是答案候选。

如果题目要求的是“最后一个等于 target 的位置”，通常也要在最后额外判断是否真的等于 target。

3. 二分查找如何避免死循环

1）什么时候会死循环

死循环通常出现在：

区间没有真正缩小
mid 取法和边界更新不匹配

例如下面这个错误写法：

while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) l = mid;
    else r = mid - 1;
}

假设：

l = 2
r = 3

那么：

mid = (2 + 3) >> 1 = 2

如果 check(mid) 为真，那么：

l = mid = 2

这时：

l 还是 2
r 还是 3

区间没有缩小，就会一直卡住。

2）为什么 `mid = (l + r) >> 1` 有时不够

因为 (l + r) >> 1 本质上是：

向下取整，也就是偏左的中点。

所以当你写的是：

l = mid

这种“保留右半边并包含 mid”的更新方式时

如果 mid 恰好等于 l，那就可能卡住。

所以不是 mid = (l + r) >> 1 错了，而是：

它必须和边界更新方式配套使用。

3）为什么有时要写成 `mid = (l + r + 1) >> 1`

因为这个写法是：

向上取整，也就是偏右的中点。

这样当你写：

l = mid;

时，即使只剩两个数：

l = 2
r = 3

也有：

mid = (2 + 3 + 1) >> 1 = 3

于是：

l = 3

区间就会缩小，不会死循环。

所以可以这样记：

如果更新写成 r = mid，通常用 偏左 mid
如果更新写成 l = mid，通常用 偏右 mid

4）左边界模板与右边界模板的区别

左边界模板通常是：

while (l < r) {
    int mid = l + ((r - l) >> 1);
    if (check(mid)) r = mid;
    else l = mid + 1;
}

特点是：

mid 偏左
满足条件时收缩右边界
找第一个满足条件的位置

右边界模板通常是：

while (l < r) {
    int mid = l + ((r - l + 1) >> 1);
    if (check(mid)) l = mid;
    else r = mid - 1;
}

特点是：

mid 偏右
满足条件时收缩左边界
找最后一个满足条件的位置

你可以直接记成一句话：

找左边界，mid 偏左
找右边界，mid 偏右

4. STL 二分接口

1）`lower_bound`

lower_bound 的含义是：

返回第一个大于等于 target 的位置。

例如：

vector<int> nums = {1, 2, 2, 4, 5};
auto it = lower_bound(nums.begin(), nums.end(), 2);

这里 it 指向第一个 2。

如果查：

auto it = lower_bound(nums.begin(), nums.end(), 3);

那么它会指向 4，因为 4 是第一个大于等于 3 的元素。

常见写法：

int pos = lower_bound(nums.begin(), nums.end(), target) - nums.begin();

2）`upper_bound`

upper_bound 的含义是：

返回第一个大于 target 的位置。

例如：

vector<int> nums = {1, 2, 2, 4, 5};
auto it = upper_bound(nums.begin(), nums.end(), 2);

这里 it 指向 4，因为 4 是第一个大于 2 的元素。

所以：

lower_bound(target)：第一个 >= target
upper_bound(target)：第一个 > target

3）`binary_search`

binary_search 的作用是：

判断某个值是否存在。

返回值是布尔值：

存在返回 true
不存在返回 false

例如：

bool ok = binary_search(nums.begin(), nums.end(), target);

它适合：

只判断“有没有”
不关心具体位置

如果你还想拿到具体位置，通常还是用：

lower_bound
或自己写二分

5. 答案二分

1）什么叫“二分答案”

答案二分不是在数组里找数，而是：

在答案范围上做二分。

也就是说：

你不知道最终答案是多少
但你知道答案一定落在某个范围内
并且这个范围具有单调性

例如：

最小可行值
最大可行值
最短时间
最大容量
最小速度

这类题通常都可以想一想能不能二分答案。

2）如何设计判定函数

答案二分最关键的是写出一个 check(x)。

这个函数表示：

当答案取 x 时，是否可行

而且这个“可行性”必须具有单调性。

常见模式是：

如果 x 可行，那么比 x 更大的也都可行
或者如果 x 可行，那么比 x 更小的也都可行

例如：

给定速度 x，能不能在 h 小时内吃完香蕉
给定容量 x，能不能在 d 天内运完货物

那么 check(x) 就是在判断这个答案是否可行。

只要 check(x) 具有单调性，就可以二分。

3）什么题能二分答案

通常满足以下特征的题可以考虑答案二分：

题目问“最小的……”“最大的……”
能把答案范围确定在 [l, r]
存在明显的单调性
可以写出 check(mid) 判断是否可行

常见关键词包括：

最小值最大化
最大值最小化
最短时间
最小速度
最大容量
最小代价

例如这些题型就很典型：

Koko 吃香蕉
在 D 天内送达包裹的能力
分割数组的最大值
最小化某种代价

6. 常见坑

1）边界更新不收缩区间

这是死循环最常见的根源。

例如：

本来应该写 l = mid + 1
却写成了 l = mid

或者：

本来应该写 r = mid - 1
却写成了 r = mid

到底能不能保留 mid，要看你定义的是：

查找具体值
左边界
右边界

不能混着写。

2）`mid` 偏左还是偏右没处理清楚

这个问题和上一条是连着的。

你要先明确自己写的是哪一类二分：

左边界模板
右边界模板

然后再决定：

mid = (l + r) >> 1
还是 mid = (l + r + 1) >> 1

最容易记的方式就是：

找左边界：mid 偏左
找右边界：mid 偏右

3）死循环

二分死循环一般都来自这两种情况：

区间没有缩小
mid 取法和更新方式不匹配

所以调试时最该检查的是：

当区间只剩两个数时会发生什么
这一轮之后 l 和 r 是否真的更接近了

4）整数溢出

不要直接写：

int mid = (l + r) >> 1;

因为如果 l 和 r 很大，l + r 可能溢出。

更稳妥的写法是：

int mid = l + ((r - l) >> 1);

如果要偏右，可以写：

int mid = l + ((r - l + 1) >> 1);

这是更推荐的写法。

5）区间定义混乱

二分查找里常见的区间定义有两种：

闭区间 [l, r]
左闭右开区间 [l, r)

两种写法都可以，但整份代码必须统一。

最怕的是：

循环条件按一种写
更新边界按另一种写
最后返回答案时又按第三种理解

这样很容易错一位。

所以写二分时最好先在脑子里明确：

每次更新后区间是否仍然合法
当前维护的是哪种区间
mid 属于哪边

三、前缀和与差分

1. 前缀和

1）什么是前缀和

前缀和（Prefix Sum）本质上是：

用一个新数组，预处理出“从开头到当前位置的累积和”。

例如原数组：

a = [1, 2, 3, 4, 5]

那么它的前缀和数组可以写成：

prefix = [0, 1, 3, 6, 10, 15]

这里：

prefix[1] = 1
prefix[2] = 1 + 2 = 3
prefix[3] = 1 + 2 + 3 = 6

也就是说：

prefix[i] 表示前 i 个元素的和。

前缀和的核心价值在于：

先花一点时间预处理
后面可以快速求任意区间和

2）一维前缀和构造

一维前缀和最常见的写法是：

vector<int> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + a[i];
}

如果原数组是从 0 开始存的，也经常写成：

vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

这样做的好处是：

prefix[0] = 0
区间和公式会更统一
不容易在边界处出错

3）区间和计算公式

如果：

prefix[i] 表示前 i 个元素的和

那么区间 [l, r] 的和就是：

sum(l, r) = prefix[r] - prefix[l - 1]

这是在原数组下标从 1 开始时的写法。

如果原数组下标从 0 开始，且你构造的是：

prefix[i + 1] = prefix[i] + nums[i]

那么区间 [l, r] 的和写成：

sum(l, r) = prefix[r + 1] - prefix[l]

这是 LeetCode 里特别常见的写法。

本质上它们都在做同一件事：

大前缀减小前缀
中间剩下的就是目标区间

4）时间复杂度分析

一维前缀和的复杂度通常是：

构造前缀和：O(n)
单次查询区间和：O(1)
空间复杂度：O(n)

所以它的优势是：

预处理一次稍微花点时间
之后每次查区间和都非常快

适合：

数组不变
查询很多次

5）适用场景

前缀和常见于以下题型：

多次查询区间和
连续子数组求和
子数组平均值
子数组是否满足某种和条件
将区间问题转化为两个前缀之差
二维矩阵求子矩阵和

只要题目里出现：

连续区间
子数组
区间和
多次查询

就可以想一想能不能用前缀和。

2. 二维前缀和

1）定义

二维前缀和是一维前缀和在矩阵上的扩展。

它的含义是：

prefix[i][j] 表示从左上角 (1,1) 到位置 (i,j) 这个矩形区域内所有元素的和。

也就是说，它维护的是一个“左上角固定”的子矩阵和。

2）构造方式

最常见的二维前缀和写法是：

vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i][j];
    }
}

如果原矩阵是从 0 开始存的，更常写成：

vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j];
    }
}

这里的公式本质上是：

上边矩形
加左边矩形
减去重复算的一块
再加当前格子

3）子矩阵求和

如果要查询子矩阵：

左上角 (x1, y1)
右下角 (x2, y2)

那么二维前缀和公式是：

sum(x1, y1, x2, y2) = prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1]

如果你用的是 0 下标原矩阵、1 下标前缀和数组，那么通常写成：

sum(x1, y1, x2, y2) = prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1]

这个公式一定要理解成：

大矩形
减上面一块
减左边一块
再加回来左上角重复减掉的那块

3. 前缀和 + 哈希

1）为什么前缀和经常和 `unordered_map` 一起出现

前缀和本身擅长的是：

快速求区间和

但很多题不只是问“某个固定区间和是多少”，而是问：

有多少个子数组和等于 k
是否存在某个子数组和等于 k
某个前缀和之前出现过几次

这时候就会发现：

区间和公式是：

sum(l, r) = prefix[r] - prefix[l - 1]

如果题目要求：

sum(l, r) = k

那就等价于：

prefix[r] - prefix[l - 1] = k

变形得到：

prefix[l - 1] = prefix[r] - k

也就是说：

当我们枚举到当前位置的前缀和 prefix[r] 时，只要知道之前有多少个前缀和等于 prefix[r] - k，就能知道有多少个合法区间。

而 unordered_map 正好可以用来：

记录某个前缀和出现过几次

所以这两者经常搭配出现。

2）前缀和计数类题目

这类题的核心通常是：

枚举当前位置
维护当前前缀和
看之前有没有某个特定值的前缀和出现过

常见写法框架是：

unordered_map<int, int> cnt;
cnt[0] = 1;

int sum = 0, ans = 0;
for (int x : nums) {
    sum += x;
    ans += cnt[sum - k];
    cnt[sum]++;
}

这里：

sum 是当前前缀和
cnt[sum - k] 表示之前有多少个前缀和等于 sum - k
每一个这样的前缀和都能形成一个和为 k 的子数组

这类题特别常见。

3）典型题：和为 K 的子数组

这是 LeetCode 560 的经典做法。

题目问的是：

有多少个连续子数组的和等于 k

核心思路就是：

枚举右端点
设当前前缀和为 sum
看之前有多少个前缀和等于 sum - k

完整代码通常写成：

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    cnt[0] = 1;

    int sum = 0, ans = 0;
    for (int x : nums) {
        sum += x;
        if (cnt.count(sum - k)) ans += cnt[sum - k];
        cnt[sum]++;
    }
    return ans;
}

这里最重要的一句是：

cnt[0] = 1;

它表示：

在开始枚举之前，有一个“前缀和为 0”的情况出现过一次

这样当某个前缀和本身就等于 k 时，也能正确计数。

4. 差分数组

1）什么是差分

差分数组可以理解为前缀和的“逆操作”。

如果原数组是 a，那么差分数组 diff 通常定义为：

diff[i] = a[i] - a[i - 1]

其中一般约定：

diff[1] = a[1]

例如：

a = [1, 3, 6, 10]

那么差分数组是：

diff = [1, 2, 3, 4]

因为：

1
3 - 1 = 2
6 - 3 = 3
10 - 6 = 4

差分的核心用途是：

把“区间整体加一个数”的操作，转化成几个位置的简单修改。

2）区间加法问题

假设要对区间 [l, r] 所有元素都加上 k。

如果直接改原数组，要做：

a[l] += k
a[l+1] += k
…
a[r] += k

这是 O(n) 的。

但如果用差分数组，只需要：

diff[l] += k;
diff[r + 1] -= k;

这样最后再对差分数组做一遍前缀和，就能还原出更新后的原数组。

例如原数组：

a = [0, 0, 0, 0, 0]

对应差分数组一开始也是：

diff = [0, 0, 0, 0, 0, 0]

如果要对区间 [2, 4] 加上 3，只需要：

diff[2] += 3;
diff[5] -= 3;

最后对 diff 做前缀和，就得到：

a = [0, 3, 3, 3, 0]

这就是差分的核心思想。

3）差分和前缀和的关系

这两个东西正好是反着的。

前缀和：从原数组得到累积和数组
差分：从原数组得到相邻元素变化量

你可以这样记：

前缀和擅长查询区间和
差分擅长处理区间修改

再换句话说：

前缀和：让查询变快
差分：让修改变快

两者经常是配套出现的。

5. 常见坑

1）前缀和数组下标偏移

这是前缀和最容易出错的地方之一。

尤其是原数组从 0 开始时，很多人会混淆：

prefix[i] 表示前 i 个元素
还是表示到下标 i 为止的元素和

更推荐的写法是：

prefix[i + 1] = prefix[i] + nums[i];

这样：

prefix[0] = 0
prefix[k] 表示前 k 个元素的和

公式会更统一。

2）`prefix[0] = 0`

这一点非常重要。

不管是一维前缀和还是二维前缀和，通常都会多开一位，并设：

prefix[0] = 0;

这样做的好处是：

区间和公式统一
不用单独特判从第一个元素开始的区间
写哈希版前缀和时也更自然

比如 LeetCode 560 里：

cnt[0] = 1;

本质上也是在表达“前缀和为 0 的情况先出现一次”。

3）区间公式写错

一维前缀和常见错误是：

把 [l, r] 写成 prefix[r] - prefix[l]
少减一位或多减一位

二维前缀和常见错误是：

少加了左上角被重复减掉的那块

所以写公式时一定要明确：

你当前的前缀和数组是怎么定义的
原数组下标从 0 开始还是从 1 开始

不要硬背公式，要和定义对应起来。

4）数组更新频繁时前缀和不合适

前缀和适合：

数组基本不变
查询很多次

因为一旦原数组某个位置改了，后面的前缀和可能都要重新算。

所以如果题目特点是：

修改很多次
查询很多次

那普通前缀和可能就不够用了，应该考虑：

差分
树状数组
线段树

你可以简单记成：

静态查询多：前缀和
区间修改多：差分
动态修改 + 动态查询：树状数组 / 线段树

四、双指针与滑动窗口

1. 双指针

双指针本质上是：

用两个位置或两个下标共同描述一个区间、一个状态或一次比较过程
通过移动这两个指针，避免重复枚举
常用于把原本 O(n^2) 的过程优化到 O(n) 或 O(n log n)

双指针常见前提包括：

数组有序
只关心连续区间
左右边界可以动态收缩或扩展
当前位置的信息能帮助决定下一步怎么移动

1）相向双指针

相向双指针指的是：

一个指针从左往右走
一个指针从右往左走
两个指针不断向中间靠拢

常见形式：

int l = 0, r = n - 1;
while (l < r) {
    ...
}

它最典型的使用场景包括：

有序数组中找两数之和
反转数组 / 字符串
判断回文
容器盛水问题
去重后的配对问题

例如在有序数组里找两个数和为 target：

如果 nums[l] + nums[r] 太小，说明左边太小，l++
如果太大，说明右边太大，r--
如果刚好等于目标，就找到答案

这种写法成立的关键是：

数组有序
当前和过小或过大时，能确定该移动哪一边

2）同向双指针

同向双指针指的是：

两个指针都从左往右移动
通常维护一个区间 [l, r]
r 负责扩展，l 负责收缩

常见形式：

int l = 0;
for (int r = 0; r < n; r++) {
    ...
    while (需要收缩窗口) {
        l++;
    }
}

它最典型的使用场景包括：

滑动窗口
最长 / 最短满足条件的子数组
去重
连续区间统计
子数组问题

同向双指针的核心思想是：

右指针不断向右扩展，加入新元素
当当前区间不合法时，再移动左指针把区间缩回合法状态
整个过程中每个元素通常只进窗口、出窗口一次，所以总复杂度往往是 O(n)

3）快慢指针

快慢指针本质上也是双指针，只不过两者移动速度不同。

常见形式包括：

慢指针一次走一步
快指针一次走两步

最典型的使用场景包括：

判断链表是否有环
找链表中点
删除数组中的重复元素
原地移除元素
数组上的“读写指针”模型

例如判断链表是否有环：

慢指针一次走一步
快指针一次走两步
如果有环，两者最终会相遇

例如数组去重：

慢指针表示“当前有效区间末尾”
快指针负责扫描新元素
当遇到新值时，把它放到慢指针后面

所以快慢指针不一定真的体现在“速度不同”上，也常表示：

一个负责读
一个负责写
一个负责扫描
一个负责维护结果边界

2. 滑动窗口

滑动窗口可以看作同向双指针的一种典型应用。

它的核心思想是：

用一个连续区间 [l, r] 表示当前窗口
右指针向右扩展窗口
左指针在需要时向右收缩窗口
在窗口移动过程中维护区间信息

滑动窗口最适合处理：

连续子数组 / 子串问题
最长 / 最短满足条件的区间
统计窗口内字符频次、元素个数、和、最值等信息

1）固定长度窗口

固定长度窗口指的是：

窗口大小始终固定为 k
每次右移一格
加入一个新元素，移除一个旧元素

常见场景包括：

长度为 k 的子数组最大和
长度为 k 的平均值
长度固定的字符串统计问题

典型写法：

int sum = 0;
for (int r = 0; r < n; r++) {
    sum += nums[r];
    if (r >= k) sum -= nums[r - k];
    if (r >= k - 1) {
        // 当前窗口是 [r-k+1, r]
    }
}

固定窗口的关键点是：

什么时候窗口刚好形成
新元素加入后，旧元素什么时候移出

2）可变长度窗口

可变长度窗口指的是：

窗口大小不固定
先通过右指针不断扩展
再根据条件决定是否收缩左边界

常见场景包括：

最长不重复子串
最短满足和至少为 target 的子数组
最多包含 k 种字符的最长子串
满足某个约束条件的连续区间

典型思路是：

扩展右边界，让窗口包含更多元素
当窗口不满足要求时，移动左边界
在满足条件时更新答案

这种问题的关键通常在于：

窗口何时合法
窗口何时必须收缩
收缩到什么程度为止

3）窗口内维护统计信息

滑动窗口之所以高效，是因为不会每次重新统计整个区间，而是：

右边界右移时，增量加入一个元素
左边界右移时，增量移除一个元素

常见需要维护的信息包括：

区间和
某个字符出现次数
不同元素个数
最大值 / 最小值
满足条件的元素个数

例如维护字符频次时，常用：

unordered_map<char, int> cnt;

例如维护窗口和时，常用：

sum += nums[r];
sum -= nums[l];

如果窗口中要维护最值，普通滑动窗口可能不够，需要配合：

单调队列

所以滑动窗口的核心不只是“左右移动”，还包括：

如何在移动过程中正确维护窗口信息。

3. 常见题型

1）最长/最短子数组

这是双指针和滑动窗口最常见的一类题。

常见问法包括：

最长满足条件的子数组
最短满足条件的子数组
最长不重复子串
最短覆盖子串

这一类题的核心通常是：

用右指针扩展区间
用左指针在必要时收缩区间
在区间合法时更新答案

经验上可以这样区分：

求最长：通常尽量扩展，在不合法时再收缩
求最短：通常一旦合法就尽量收缩

2）去重

去重类问题常见于：

删除有序数组中的重复项
最长不含重复字符的子串
保留每种元素最多若干次
原地移除某个值

如果是数组原地去重，常用快慢指针：

快指针扫描
慢指针维护有效结果区间

如果是字符串或子数组中的“窗口去重”，常用滑动窗口 + 哈希表：

右边加入字符
左边移除重复影响
保证窗口内始终合法

3）满足某个条件的连续区间

这类题往往有很明显的“窗口感”。

例如：

和大于等于 target 的最短子数组
乘积小于 k 的子数组个数
至多包含 k 种字符的最长子串
某个指标不超过限制的最长区间

这类题的核心是：

当前窗口是否满足条件
条件在窗口扩大后会怎么变化
什么时候应该收缩左边界

很多时候，只要题目强调：

连续
子数组 / 子串
满足某个区间条件

就应该先想一想能不能用双指针或滑动窗口。

4. 常见坑

1）左边界和右边界更新顺序

这是滑动窗口里最容易写乱的地方。

尤其要想清楚：

是先加入 nums[r]，再判断是否合法
还是先判断，再移动 r
收缩左边界时，是先减统计量再 l++
还是先 l++ 再减

顺序一错，窗口统计信息就会错。

写代码时最好始终保持一种固定节奏，例如：

先加入右边元素
再检查是否合法
不合法时收缩左边界
最后更新答案

2）窗口收缩条件写错

这是可变窗口最常见的问题之一。

比如题目要求：

窗口内不能有重复字符
窗口和必须大于等于 target
窗口内不同元素个数不能超过 k

那你要非常清楚：

什么时候收缩
收缩到什么时候为止

很多错误都来自：

本来该写 while
却写成了 if

因为窗口可能需要连续收缩多次，直到重新合法，而不是只缩一次。

3）统计变量忘记回退

窗口移动时，如果维护了：

频次数组
哈希表
区间和
不同元素个数

那左边界右移时一定要同步更新这些信息。

例如：

cnt[s[l]]--;
l++;

或者：

sum -= nums[l];
l++;

如果只移动了指针，忘记把统计量减回来，后续窗口状态就会一直错。

所以滑动窗口的一个核心原则就是：

元素进窗口时加一次，出窗口时减一次。

五、栈、单调栈、队列、单调队列、堆

1. 栈

1）基本概念

栈（Stack）是一种 后进先出（LIFO，Last In First Out）的数据结构。

可以把它理解为：

新进入的元素放在最上面
每次只能访问和删除最上面的元素
最后进去的元素最先出来

最常见的基本操作包括：

push：入栈
pop：出栈
top：查看栈顶元素

栈特别适合处理这类问题：

最近加入的元素优先处理
存在明显的嵌套关系
需要“回退到上一个状态”

2）典型用途

栈常见于以下场景：

括号匹配
表达式求值
去除相邻重复字符
单调栈
函数调用过程的模拟
DFS 的非递归写法
需要维护“最近一个满足条件元素”的问题

可以简单记成：

只关心“最后加入的那个元素”时，往往可以想到栈

3）括号匹配

括号匹配是栈最经典的应用。

例如字符串：

"()[]{}" 是合法的
"(]" 是不合法的
"([)]" 也是不合法的

基本思路是：

遇到左括号就入栈
遇到右括号就检查栈顶是否是对应的左括号
如果不是，说明不匹配
最后栈为空，说明全部匹配成功

典型写法：

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char t = st.top();
            st.pop();
            if (c == ')' && t != '(') return false;
            if (c == ']' && t != '[') return false;
            if (c == '}' && t != '{') return false;
        }
    }
    return st.empty();
}

这类题的核心在于：

右括号要和“最近的、还没匹配过的左括号”对应
这正好符合栈的后进先出特性

4）表达式处理

栈也很适合处理表达式问题，例如：

后缀表达式求值
中缀表达式转后缀表达式
带括号的表达式计算
逆波兰表达式

例如后缀表达式：

["2","1","+","3","*"]

表示：

(2 + 1) * 3

处理方法通常是：

遇到数字就入栈
遇到运算符就弹出两个数进行计算
再把结果压回栈中

栈在表达式处理中常见的原因是：

运算有先后顺序
括号有嵌套关系
局部结果需要临时保存

2. 单调栈

1）适用场景

单调栈本质上是：

在普通栈的基础上
让栈内元素始终保持单调递增或单调递减

它特别适合处理这类问题：

找左边第一个更大 / 更小的元素
找右边第一个更大 / 更小的元素
维护“最近一个更优元素”
一边遍历，一边删除不可能再有用的元素

单调栈通常适用于：

数组题
连续区间题
想找“最近更大 / 更小”的问题

2）找左边第一个更大/更小

这一类问题的常见问法是：

对每个位置，找左边离它最近的更大元素
对每个位置，找左边离它最近的更小元素

以“找左边第一个更小元素”为例：

从左到右扫描数组
用一个单调递增栈保存候选元素
当前元素进来前，先把栈里不可能成为答案的元素弹掉

例如数组：

[2, 1, 4, 3]

处理到 4 时：

左边最近更小的是 1

处理到 3 时：

左边最近更小的是 1

这类题的核心是：

栈顶始终是“离当前最近、且仍可能成为答案”的元素

3）找右边第一个更大/更小

这一类问题的常见问法是：

对每个位置，找右边第一个更大的元素
对每个位置，找右边第一个更小的元素

最经典的是“下一个更大元素”。

例如数组：

[2, 1, 2, 4, 3]

对于每个位置，找右边第一个更大的数：

2 -> 4
1 -> 2
2 -> 4
4 -> 不存在
3 -> 不存在

常见做法有两种：

从左到右扫，用当前元素去更新前面还没找到答案的位置
从右到左扫，维护右边的单调栈

例如从左到右写“右边第一个更大元素”：

vector<int> res(n, -1);
stack<int> st; // 存下标

for (int i = 0; i < n; i++) {
    while (!st.empty() && nums[i] > nums[st.top()]) {
        res[st.top()] = nums[i];
        st.pop();
    }
    st.push(i);
}

4）典型题型

单调栈常见于以下题型：

每日温度
下一个更大元素
下一个更小元素
柱状图中最大的矩形
接雨水
子数组最小值之和
维护某个方向上的最近更优元素

你可以把单调栈的信号总结成一句话：

如果题目在问“最近的更大 / 更小”，优先想到单调栈。

3. 队列

1）BFS

队列（Queue）是一种 先进先出（FIFO，First In First Out）的数据结构。

它在图论和搜索里最典型的用途就是 BFS。

因为 BFS 的本质是：

先扩展距离近的状态
再扩展距离远的状态

这刚好符合队列“谁先进来谁先处理”的特点。

典型框架：

queue<int> q;
q.push(start);

while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : g[u]) {
        if (!vis[v]) {
            vis[v] = true;
            q.push(v);
        }
    }
}

2）层序遍历

队列在二叉树中最典型的用途是层序遍历。

因为层序遍历要求：

先访问根节点
再访问下一层
再访问下一层

这本质上也是 BFS。

典型写法：

queue<TreeNode*> q;
q.push(root);

while (!q.empty()) {
    int sz = q.size();
    vector<int> level;

    while (sz--) {
        TreeNode* node = q.front();
        q.pop();

        level.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }

    ans.push_back(level);
}

这里每次先记录 sz，就是为了把同一层的节点一起处理掉。

3）普通模拟

除了 BFS 和层序遍历，队列也常用于普通模拟题。

例如：

排队问题
任务调度
按时间顺序处理事件
数据流按到达顺序处理

只要题目特征是：

谁先来谁先处理
按顺序依次出队

就可以想到队列。

4. 单调队列

1）为什么要用单调队列

普通队列能保证先进先出，但不能高效维护区间最值。

例如滑动窗口最大值问题：

每次窗口右移一格
想快速知道窗口里的最大值

如果每次都重新扫一遍窗口，复杂度会很高。

单调队列的作用就是：

在队列中维护一个单调性
保证队头始终是当前窗口的最值
从而把每次求最值的复杂度降下来

所以单调队列的核心用途是：

维护一个滑动区间内的最大值或最小值

2）滑动窗口最大值

这是单调队列最经典的题型。

例如数组：

[1, 3, -1, -3, 5, 3, 6, 7]

窗口大小 k = 3

每个窗口的最大值分别是：

[3, 3, 5, 5, 6, 7]

做法是：

队列里通常存下标
保证队列对应的值单调递减
新元素进入时，把队尾所有比它小的元素弹掉
队头如果已经滑出窗口，也要弹掉
队头就是当前窗口最大值

典型写法：

deque<int> dq;
vector<int> ans;

for (int i = 0; i < nums.size(); i++) {
    while (!dq.empty() && nums[dq.back()] <= nums[i]) {
        dq.pop_back();
    }
    dq.push_back(i);

    while (!dq.empty() && dq.front() <= i - k) {
        dq.pop_front();
    }

    if (i >= k - 1) {
        ans.push_back(nums[dq.front()]);
    }
}

3）维护区间最值

单调队列不仅能维护最大值，也能维护最小值。

区别只是：

维护最大值：队列单调递减
维护最小值：队列单调递增

它适合这类题：

滑动窗口最大值 / 最小值
动态维护某个连续区间的最值
DP 优化中的区间最值维护

你可以把单调队列记成：

用来维护滑动窗口中的最值
本质上是队列 + 单调性

5. 堆与优先队列

1）大顶堆与小顶堆

堆是一种特殊的完全二叉树结构，最常见的是：

大顶堆：父节点大于等于子节点，堆顶是最大值
小顶堆：父节点小于等于子节点，堆顶是最小值

在 C++ 里通常通过 priority_queue 使用堆。

默认写法：

priority_queue<int> pq;

这是大顶堆，top() 是最大值。

如果想写小顶堆：

priority_queue<int, vector<int>, greater<int>> pq;

这时 top() 是最小值。

堆的核心作用是：

快速拿到当前最大值或最小值

2）Top K

堆特别适合解决 Top K 问题。

例如：

第 K 大元素
前 K 个高频元素
前 K 小元素

最经典的思路是：

用一个大小为 k 的小顶堆维护当前前 k 大元素
堆顶始终是这 k 个元素里最小的那个
如果来了更大的元素，就把堆顶弹掉再加入新元素

这样最后堆里留下的就是前 k 大。

Top K 之所以适合用堆，是因为：

不需要整体排序
只需要维护局部最优的 k 个元素

3）动态维护最值

堆的一个核心应用就是：

元素会动态加入
过程中要不断取当前最大值或最小值

例如：

数据流中的中位数
会议室 / 任务调度
合并多个有序结构
每一步都取当前最优元素

这类问题里，堆比“每次都重新排序”高效得多。

4）贪心中的应用

很多贪心题的本质是：

每一步都从当前候选中选一个最优的

如果这个“最优”需要动态维护，那么往往就会想到堆。

例如：

每次选最小代价
每次选结束时间最早的任务之一
每次取最小边 / 最小权值
合并代价最小的两个元素

堆在贪心中的作用可以理解为：

帮你快速拿到“当前最优选择”
并在选择后继续维护剩余候选集合

你可以把这一节最后记成一句话：

栈关注最近加入的元素
队列关注最早加入的元素
单调栈关注最近更大 / 更小
单调队列关注滑动窗口最值
堆关注动态最值和当前最优选择

六、树状数组与线段树

这一部分是区间问题的重要专题。

1. 树状数组

1）适合解决什么问题

树状数组（Binary Indexed Tree，简称 BIT）主要适合处理这类问题：

单点更新 + 前缀查询
单点更新 + 区间查询
需要动态维护前缀和的信息
需要多次修改数组中的某个位置，同时频繁查询前缀和或区间和

它最经典的用途就是：

修改某个位置的值
查询前 i 个元素的和

如果要求的是区间和 [l, r]，通常可以转化成：

sum(r) - sum(l - 1)

所以树状数组最擅长的是：

前缀型问题
可拆成两个前缀差的问题

如果题目需要维护的信息比较简单，比如：

区间和
频次数组
前缀计数

那树状数组通常比线段树更短、更好写。

2）单点更新、前缀查询

树状数组的核心操作只有两个：

add(x, k)：给位置 x 加上 k
sum(x)：查询前 x 个元素的和

其核心思想是：

用一个数组 tree[] 来维护若干区间的信息
每个位置管一段区间
通过二进制中的最低位 lowbit(x) 快速跳转

lowbit(x) 通常写成：

int lowbit(int x) {
    return x & -x;
}

它表示：

x 二进制表示中最低位的那个 1 所对应的值

例如：

lowbit(6)，因为 6 = 110，所以结果是 2
lowbit(8)，因为 8 = 1000，所以结果是 8

单点更新通常写成：

void add(int x, int k) {
    while (x <= n) {
        tree[x] += k;
        x += lowbit(x);
    }
}

前缀查询通常写成：

int sum(int x) {
    int res = 0;
    while (x > 0) {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

区间和查询可以写成：

int query(int l, int r) {
    return sum(r) - sum(l - 1);
}

3）时间复杂度

树状数组的常见操作复杂度如下：

单点更新：O(log n)
前缀查询：O(log n)
区间查询：O(log n)
建树：朴素做法通常是 O(n log n)

如果只是从空数组开始不断插入和修改，通常直接记：

更新快
查询快
实现简单
空间复杂度 O(n)

4）和线段树的区别

树状数组和线段树都能处理动态区间问题，但侧重点不同。

树状数组更适合：

单点更新
前缀查询
区间和这类可由前缀差得到的问题
信息维护比较简单的场景

线段树更适合：

区间查询更复杂的信息
区间最大值 / 最小值
区间更新
懒标记
查找区间内第一个满足条件的位置

可以简单理解为：

树状数组更轻量，代码更短
线段树更通用，功能更强

如果题目只要求：

单点修改
区间和

通常优先考虑树状数组。

如果题目要求：

区间更新
维护区间最值
复杂条件查询

通常更适合线段树。

2. 线段树基础

1）什么是线段树

线段树是一种用于维护区间信息的数据结构。

可以把它理解为：

把整个数组区间不断二分
每个节点负责维护一个子区间的信息
根节点维护整个区间
叶子节点维护单个位置

例如数组下标范围是 [1, n]，那么：

根节点维护 [1, n]
左儿子维护 [1, mid]
右儿子维护 [mid + 1, n]

这样就形成了一棵二叉树结构。

线段树的核心价值在于：

能够高效维护区间信息
在修改后快速更新受影响的部分
查询时只访问少量相关节点

2）树的结构

线段树通常是一棵二叉树。

每个节点一般会维护：

当前节点对应的区间左端点 l
当前节点对应的区间右端点 r
当前区间的信息，比如：
- 区间和
- 区间最大值
- 区间最小值
- 其他自定义信息

常见写法是用数组模拟树：

struct Node {
    int l, r;
    int sum;
} tr[4 * N];

为什么通常开 4 * N：

因为线段树是递归二叉划分
开 4 * N 基本可以保证空间足够

如果当前节点编号为 u，那么通常：

左儿子编号：u << 1
右儿子编号：u << 1 | 1

3）适用场景

线段树常见于以下题型：

区间和查询
区间最大值 / 最小值查询
单点修改
区间修改
动态维护数组信息
查找区间内第一个满足条件的位置
需要大量区间查询和更新的题

一般来说，只要题目里同时出现：

区间
动态更新
多次查询

就可以考虑线段树。

4）构建复杂度

线段树建树通常是递归完成的。

如果每个节点的信息都能由左右子节点信息合并得到，那么：

建树时间复杂度：O(n)
空间复杂度：O(n)

更准确地说，空间通常开到 4n。

这是因为：

每个位置最终只会作为一个叶子节点出现
整棵树节点数和 n 同阶

3. 线段树的核心操作

1）建树

建树就是递归地把区间 [l, r] 划分成左右两半，并为每个节点维护对应信息。

典型写法如下：

void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    if (l == r) {
        tr[u].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

其中 push_up(u) 的作用是：

用左右儿子的值更新当前节点

例如维护区间和时：

void push_up(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

2）区间查询

区间查询的核心思路是：

如果当前节点区间被目标区间完全包含，直接返回当前节点信息
如果只部分重合，就递归到左右子区间继续查

例如查询区间和：

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;    int mid = (tr[u].l + tr[u].r) >> 1;
    int res = 0;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

3）单点更新

单点更新就是修改某一个位置的值，然后一路回溯更新祖先节点。

例如把位置 x 加上 v：

void modify(int u, int x, int v) {
    if (tr[u].l == tr[u].r) {
        tr[u].sum += v;
        return;
    }    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) modify(u << 1, x, v);
    else modify(u << 1 | 1, x, v);    push_up(u);
}

4）区间更新

如果只是单点更新，那么递归下去就够了。

但如果是区间更新，比如：

给 [l, r] 所有元素都加上 k

如果每次都递归到叶子节点，会很慢。
这时通常需要配合 懒标记 来优化。

也就是说：

区间更新是线段树的强项之一
真正高效实现时通常离不开懒标记

4. 懒标记

1）为什么需要懒标记

假设要对一个很大的区间 [l, r] 整体加上 k。

如果你把这个区间里的每个点都一个个改掉，那么效率会很低，最坏会退化成 O(n)。

懒标记的核心思想是：

先不急着把修改下放到所有子节点
只在当前节点记录“这一整段已经被加过了”
等到真正需要访问子节点时，再把标记传下去

所以懒标记本质上是一种：

延迟更新
按需下传

的思想。

2）懒标记的含义

懒标记一般表示：

当前节点对应的整个区间还欠着一个更新没有下发到子节点

例如维护区间加法时，常见写法是：

tr[u].sum += (tr[u].r - tr[u].l + 1) * add;
tr[u].lazy += add;

这表示：

当前节点的区间和已经更新了
但它的左右子节点还没真正改
以后如果要继续往下访问，再把这个 lazy 往下传

3）下传与维护

下传通常叫 push_down()。

它的作用是：

把当前节点存着的懒标记传给左右儿子
同时更新左右儿子的区间信息
然后清空当前节点的懒标记

例如区间加法时：

void push_down(int u) {
    if (tr[u].lazy) {
        int lazy = tr[u].lazy;
        tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * lazy;
        tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * lazy;
        tr[u << 1].lazy += lazy;
        tr[u << 1 | 1].lazy += lazy;
        tr[u].lazy = 0;
    }
}

通常在以下场景会调用 push_down()：

查询前
更新前
继续递归访问左右子树前

而 push_up() 的作用是：

子节点更新后，重新维护父节点信息

所以可以这样记：

push_up：子到父
push_down：父到子

5. 线段树常见题型

1）区间和

这是最基础的线段树题型。

适合场景：

数组会被动态修改
要多次查询某段区间的和

如果只有单点更新，也可以和树状数组对比考虑。

2）区间最大值 / 最小值

这类题型通常要求：

维护区间最值
支持单点或区间修改
查询某个区间的最大值或最小值

这是树状数组不擅长、线段树很擅长的场景。

3）区间内找第一个满足条件的位置

这类题通常不是简单求和，而是：

在某段区间里找第一个大于等于某值的位置
找第一个满足某条件的下标

这类查询通常要依赖线段树维护的信息，并在树上二分或递归下探。

这是线段树非常经典的一类进阶题。

4）动态更新数组

只要题目特点是：

数组内容会变
需要多次查询区间信息
不能每次都重新扫一遍区间

基本都可以考虑线段树。

6. 常见坑

区间左右边界写错

这是线段树最容易出错的地方之一。

尤其要反复确认：

当前节点维护的是闭区间还是半开区间
mid 的划分方式
左区间是不是 [l, mid]
右区间是不是 [mid + 1, r]

只要这里错一个，后面整棵树都会错。

递归终止条件写错

最常见的终止条件是：

if (l == r)

这表示已经递归到叶子节点。

如果终止条件没写对，可能会导致：

无限递归
少更新一个点
漏掉某些区间

下标从 0 开始还是从 1 开始没统一

树状数组通常最常见的是 从 1 开始。

因为：

lowbit(0) = 0
如果从 0 开始写，容易出问题

线段树倒是可以从 0 开始，也可以从 1 开始，但整份代码必须统一。

最怕的是：

原数组从 0 开始
树状数组按 1 开始写
查询时又忘了转换

这样非常容易错。

`push_up` / `push_down` 漏写

这是线段树题里非常高频的 bug 来源。

子节点改完之后忘记 push_up
递归下去之前忘记 push_down
更新完懒标记但没同步维护区间值

这些都会导致结果不对，而且有时很难第一眼看出来

七、哈希专题

1. 哈希表基础

1）为什么哈希适合做题

哈希表最核心的价值是：

可以把“值”直接映射到一个位置，从而快速查找。

你可以把它理解为：

普通数组是“下标 -> 值”
哈希表是“键 -> 值”

例如：

想统计某个数字出现了几次
想判断某个数是否出现过
想根据一个值快速找到另一个值
想记录某个前缀和出现过几次

这些问题如果用暴力做，往往要反复遍历，复杂度容易到 O(n^2)。
而哈希表常常能把这些操作降到平均 O(1)。

所以哈希特别适合这类题：

查找是否存在
统计频次
维护映射关系
记录状态是否访问过
前缀和计数

在 LeetCode 里，哈希几乎是最高频工具之一。

2）时间复杂度优势

哈希表最常见的容器是：

unordered_map
unordered_set

它们在平均情况下的常见复杂度是：

插入：O(1)
删除：O(1)
查找：O(1)

这就是哈希最大的优势。

例如你想判断某个数是否已经出现过：

暴力做法可能是：

扫一遍之前所有元素
每次查询 O(n)

如果用哈希集合：

unordered_set<int> st;
if (st.count(x)) {
    // x 已经出现过
}

这通常就是平均 O(1)。

所以很多题里，哈希能把：

O(n^2) 降到 O(n)
O(n log n) 降到 O(n)

当然，这里要注意：

哈希的 O(1) 是平均意义下的，不是严格最坏情况。

3）冲突与退化

哈希表的底层本质上是：

先通过哈希函数，把 key 映射到某个桶（bucket）
再把元素存到对应桶里

问题在于：

不同的 key 可能会被映射到同一个桶，这就叫 哈希冲突。

例如：

key1 和 key2
它们哈希值不同或相同，但最后落到同一个桶

这时哈希表就需要在这个桶里进一步区分它们。

如果冲突太多，就会出现性能退化：

本来平均 O(1) 的查找
可能退化到最坏 O(n)

所以哈希表的复杂度通常写成：

平均 O(1)
最坏 O(n)

不过在绝大多数刷题场景里，我们通常还是按平均复杂度来用它。

你只要知道：

哈希很快
但不是无条件绝对快
本质上依赖哈希函数和冲突情况

就够了。

2. 常见题型

1）频次统计

这是哈希最经典的用途之一。

题目特征通常是：

某个元素出现了多少次
某个字符出现频率如何
谁出现次数最多 / 最少
统计某个前缀和、某个状态、某个值的出现次数

最常见写法：

unordered_map<int, int> cnt;
for (int x : nums) {
    cnt[x]++;
}

如果是字符统计：

unordered_map<char, int> cnt;
for (char c : s) {
    cnt[c]++;
}

哈希之所以特别适合频次统计，是因为：

key 表示元素本身
value 表示出现次数

不需要先排序，也不需要嵌套遍历。

典型题型包括：

两数之和
前 K 个高频元素
有效的字母异位词
最长连续序列中的辅助统计
各种字符计数题

2）判重

哈希表也非常适合做“去重”和“判重”。

题目特征通常是：

某个元素有没有出现过
某个状态有没有访问过
是否存在重复元素
搜索过程中某个状态是否已经处理过

这时候通常用：

unordered_set

例如判断数组中是否有重复元素：

unordered_set<int> st;
for (int x : nums) {
    if (st.count(x)) return true;
    st.insert(x);
}
return false;

在 BFS / 图搜索中，也经常用哈希集合判重：

unordered_set<string> vis;
if (!vis.count(state)) {
    vis.insert(state);
    q.push(state);
}

所以你可以记成：

只关心“有没有”时，优先想 unordered_set
既要判断，又要顺手统计次数时，优先想 unordered_map

3）映射关系

哈希表很适合维护“一个值对应另一个值”的关系。

也就是：

key -> value

例如：

数字映射到下标
字符映射到出现位置
单词映射到频次
节点映射到状态
某个模式映射到另一个结构

最经典例子就是“两数之和”：

unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
    int need = target - nums[i];
    if (mp.count(need)) {
        return {mp[need], i};
    }
    mp[nums[i]] = i;
}

这里哈希表存的是：

数值 -> 下标

这就是典型映射关系题。

所以当题目里出现：

“根据某个值快速找到另一个东西”
“记录某个值第一次 / 最后一次出现的位置”
“建立一一对应或多对一对应关系”

都可以优先考虑哈希。

4）前缀和计数

这是哈希和前缀和最经典的结合场景。

题目特征通常是：

问有多少个子数组 / 子串满足某种和条件
需要统计“之前某个前缀状态出现过几次”

以“和为 K 的子数组”为例：

如果当前前缀和是 sum，那么只要之前出现过前缀和：

sum - k

就说明存在一段区间和为 k。

所以我们用哈希表记录：

某个前缀和出现过几次

典型写法：

unordered_map<int, int> cnt;
cnt[0] = 1;int sum = 0, ans = 0;
for (int x : nums) {
    sum += x;
    ans += cnt[sum - k];
    cnt[sum]++;
}

这里哈希表的作用不是普通查找，而是：

记录历史前缀和频次
快速统计符合条件的区间个数

3. 常见坑

1）`operator[]` 副作用

这是 unordered_map 最容易踩的坑之一。

例如：

unordered_map<int, int> mp;
cout << mp[10];

很多人以为这只是“访问一下”。

其实它会做两件事：

访问 key = 10
如果这个 key 不存在，就自动插入一个默认值

也就是说，上面那句执行完以后，哈希表里会多一个：

10 -> 0

如果 value 是 string，就会插入空字符串；如果 value 是 vector<int>，就会插入空数组。

所以如果你只是想判断 key 是否存在，优先写：

mp.find(key);
mp.count(key);
mp.contains(key);

而不是直接用：

mp[key]

你可以这样记：

mp[key]：可能会插入
find / count / contains：只查，不插

2）自定义类型哈希

基础类型通常可以直接用在哈希表里，比如：

int
long long
char
string

但如果你想把这些类型当 key：

pair<int, int>
自定义结构体
自定义类

很多情况下就不能直接用，需要自己写哈希函数。

例如你想写：

unordered_map<pair<int, int>, int> mp;

很多环境下是不能直接通过编译的。

这时候通常要提供一个自定义哈希器。

例如：

struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};

unordered_map<pair<int, int>, int, PairHash> mp;

这个坑在 LeetCode 里很常见，尤其是你想把：

坐标
状态对
(x, y)
(node, mask)

这种结构直接塞进 unordered_map 或 unordered_set 的时候。

3）遍历无序

unordered_map 和 unordered_set 最重要的特征之一就是：

无序。

这里的无序表示：

不按 key 大小排序
也不保证按插入顺序遍历

例如：

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

你遍历它时，结果不一定是：

1 2 3

也不一定是：

3 1 2

同理：

unordered_map<int, int> mp;
mp[3] = 30;
mp[1] = 10;
mp[2] = 20;

遍历时 key 的顺序也是不确定的。

所以如果题目要求：

按顺序处理
找前驱后继
做范围查询
维护自动有序

那就不该用哈希，而应该考虑：

map
set

你可以简单记成：

哈希负责快
有序结构负责顺序

八、树与二叉树

1. 二叉树遍历

二叉树遍历本质上是在回答：

先访问谁
后访问谁
当前节点、左子树、右子树的处理顺序是什么

二叉树遍历是树题最基础的部分，很多题本质上都是在遍历过程中顺手维护答案。

1）前序

前序遍历的顺序是：

先访问当前节点
再遍历左子树
再遍历右子树

顺序可以记成：

根 -> 左 -> 右

递归写法：

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

前序遍历常用于：

先处理当前节点，再处理子树的问题
树的序列化
复制树结构
构造题中的递归展开

2）中序

中序遍历的顺序是：

先遍历左子树
再访问当前节点
再遍历右子树

顺序可以记成：

左 -> 根 -> 右

递归写法：

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

中序遍历最重要的性质是：

二叉搜索树的中序遍历结果是递增有序的

所以它特别适合：

判断 BST 是否合法
求二叉搜索树第 k 小元素
把 BST 转成有序序列

3）后序

后序遍历的顺序是：

先遍历左子树
再遍历右子树
最后访问当前节点

顺序可以记成：

左 -> 右 -> 根

递归写法：

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

后序遍历特别适合这类问题：

当前节点的答案依赖左右子树
要先处理完子树，再回到当前节点
树形 DP
求树高、直径、平衡性

你可以把后序遍历理解成：

先拿到左右孩子的信息，再更新当前节点

4）层序

层序遍历的顺序是：

一层一层从上到下遍历
每层通常从左到右访问

它本质上就是二叉树上的 BFS，所以通常要用队列。

典型写法：

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (!root) return ans;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;

        while (sz--) {
            TreeNode* node = q.front();
            q.pop();

            level.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        ans.push_back(level);
    }

    return ans;
}

层序遍历常用于：

按层输出树
最短步数类树问题
求每层统计信息
判断完全二叉树
BFS 风格的树题

2. 二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一类特殊的二叉树。

它的核心不是“有两个孩子”，而是“满足有序性”。

1）性质

二叉搜索树的核心性质是：

左子树所有节点值都小于当前节点值
右子树所有节点值都大于当前节点值
左右子树本身也都是二叉搜索树

这意味着：

查找时可以像二分一样决定往左还是往右
中序遍历结果有序

例如这棵树：

      5
    /   \
   3     7
  / \   / \
 2   4 6   8

它就是 BST，因为：

左边都比 5 小
右边都比 5 大
每棵子树内部也满足同样性质

BST 的一个重要结论是：

中序遍历 = 升序序列

2）查找

在 BST 中查找一个值时，可以利用大小关系剪枝。

思路是：

如果当前节点值等于目标值，找到
如果目标值小于当前节点值，去左子树找
如果目标值大于当前节点值，去右子树找

递归写法：

TreeNode* searchBST(TreeNode* root, int val) {
    if (!root || root->val == val) return root;
    if (val < root->val) return searchBST(root->left, val);
    return searchBST(root->right, val);
}

这和普通二叉树查找的区别在于：

普通二叉树可能要整棵树都搜
BST 能利用有序性快速排除一半子树

3）插入

BST 插入的思路和查找类似：

如果目标值小于当前节点，就往左插
如果目标值大于当前节点，就往右插
如果走到空节点，就把新节点放在这里

递归写法：

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insertIntoBST(root->left, val);
    else if (val > root->val) root->right = insertIntoBST(root->right, val);
    return root;
}

插入之后 BST 仍然要保持原有性质。

4）删除

BST 删除是相对更难的一部分，因为要分类讨论。

删除一个节点时，通常分三种情况：

没有孩子
直接删掉
只有一个孩子
用它的孩子顶替它
有两个孩子
通常用它的中序后继或中序前驱替换它，再删除那个替代节点

最常见做法是：

找右子树里最小的节点，作为当前节点的后继
用后继值覆盖当前节点
再去右子树删除那个后继节点

这是 BST 删除的核心难点。

3. 常见题型

1）路径问题

树上的路径题非常常见。

常见问法包括：

根到叶子路径
路径和是否等于某个值
所有路径和
最大路径和
从某个节点到某个节点的路径信息

这类题常用的方法是：

DFS
回溯
递归返回路径相关信息

例如“根到叶子路径和”常见思路是：

往下 DFS
累加当前路径和
到叶子时判断是否满足条件

路径题的关键通常是区分：

路径是否必须从根开始
路径是否必须到叶子结束
路径是否必须连续向下
路径能不能拐弯

这些条件一变，写法就会变很多。

2）最近公共祖先

最近公共祖先（LCA，Lowest Common Ancestor）是树题高频考点。

定义是：

对于两个节点 p 和 q
它们最近的公共祖先，就是离它们最近、同时是二者祖先的那个节点

在普通二叉树中，经典递归思路是：

如果当前节点为空，返回空
如果当前节点就是 p 或 q，返回当前节点
分别在左右子树找
如果左右都找到了，说明当前节点就是最近公共祖先
如果只有一边找到了，就把那一边返回上去

递归写法：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left && right) return root;
    return left ? left : right;
}

如果是在 BST 中，LCA 会更简单，因为可以利用大小关系判断往哪边走。

3）树高 / 直径

树高和直径都是树题里的基础概念。

树高 / 最大深度
表示从当前节点往下走，到最深叶子节点的最长路径长度。

经典写法：

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

树的直径
表示树中任意两个节点之间最长路径的长度。

做直径题时，常见思路是：

后序遍历
对每个节点求左右子树高度
当前节点处可能形成一条路径：leftHeight + rightHeight
用全局变量维护最大值

所以树高 / 直径这一类题通常都适合：

后序遍历
DFS 返回子树信息

4）构造树

构造树类题型通常会给你一些遍历结果或结构信息，让你把树还原出来。

最典型的题包括：

前序 + 中序构造二叉树
中序 + 后序构造二叉树
有序数组转平衡 BST
排序链表转平衡 BST

例如“前序 + 中序构造树”的核心思路是：

前序第一个元素一定是根
在中序里找到根的位置
根左边是左子树
根右边是右子树
递归构造左右子树

这类题的关键通常是：

先找根
再确定左右区间
递归构建

所以它本质上是“利用遍历顺序信息递归分治”。

九、图论

1. 图的存储

1）邻接表

邻接表是图论里最常用的存图方式。

它的核心思想是：

对于每个点，记录它能直接到达哪些点
每个点维护一个“邻居列表”

如果图有 n 个点，可以写成：

vector<vector<int>> g(n);
g[u].push_back(v);

如果是无向图，通常要双向存边：

g[u].push_back(v);
g[v].push_back(u);

如果是带权图，可以写成：

vector<vector<pair<int, int>>> g(n);
g[u].push_back({v, w});

这里：

v 表示终点
w 表示边权

邻接表的优点是：

空间效率高
遍历某个点的所有出边很方便
特别适合稀疏图

邻接表的空间复杂度通常是：

O(n + m)

其中：

n 是点数
m 是边数

在 LeetCode 里，大多数图题默认都优先用邻接表。

2）邻接矩阵

邻接矩阵是另一种常见存图方式。

它的核心思想是：

用一个二维数组 g[i][j] 表示点 i 和点 j 之间是否有边，或者边权是多少

例如无权图可以写成：

vector<vector<int>> g(n, vector<int>(n, 0));
g[u][v] = 1;

如果是带权图，可以写成：

vector<vector<int>> g(n, vector<int>(n, INF));
g[u][v] = w;

邻接矩阵的优点是：

判断两点之间是否有边非常快
写法直观
对点数较小的稠密图比较方便

它的缺点是：

空间复杂度高，为 O(n^2)
如果图很稀疏，会浪费很多空间

所以一般来说：

稠密图、小规模图，可以考虑邻接矩阵
稀疏图、大多数 LeetCode 图题，优先邻接表

2. 图遍历

1）DFS

DFS 是深度优先搜索，特点是：

一条路先尽量走到底
走不通再回退
常用递归实现

图上的 DFS 通常要注意两件事：

图可能有环
所以需要 visited 数组防止重复访问

基本写法如下：

vector<vector<int>> g;
vector<bool> vis;

void dfs(int u) {
    vis[u] = true;
    for (int v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

DFS 常用于：

判断连通性
统计连通块个数
图遍历
拓扑排序的 DFS 写法
树和图上的递归搜索

如果题目问：

某个点能不能到另一个点
有几个连通分量
某个区域能扩展到哪里

通常都可以考虑 DFS。

2）BFS

BFS 是广度优先搜索，特点是：

从起点开始一层一层向外扩展
借助队列实现
很适合求无权图最短路

图上的 BFS 基本写法如下：

vector<vector<int>> g;
vector<bool> vis;
queue<int> q;

q.push(start);
vis[start] = true;

while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : g[u]) {
        if (!vis[v]) {
            vis[v] = true;
            q.push(v);
        }
    }
}

BFS 常用于：

无权图最短路
按层扩展状态
最短步数问题
判断可达性
多源扩展问题

如果题目里出现：

最少几步
最短路径长度
一圈一圈扩展

通常优先考虑 BFS。

3. 最短路

1）Dijkstra

Dijkstra 算法用于求 单源最短路，适用于：

边权非负
从一个起点出发，到其他所有点的最短距离

它的核心思想是：

每次取出当前“距离起点最近、且还没确定最短路”的点
用这个点去更新它邻居的距离

常见写法是配合优先队列：

vector<vector<pair<int, int>>> g(n);
vector<int> dist(n, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

dist[start] = 0;
pq.push({0, start});

while (!pq.empty()) {
    auto [d, u] = pq.top();
    pq.pop();

    if (d > dist[u]) continue;

    for (auto [v, w] : g[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

这里优先队列里存的是：

当前最短距离
对应节点编号

Dijkstra 的时间复杂度通常记为：

邻接表 + 堆优化：O(m log n)

它适合：

稀疏图
非负权图
求最短路径长度

2）BFS 最短路

如果图是 无权图，或者每条边权都相同，比如都等于 1，那么最短路就可以直接用 BFS。

因为 BFS 本身就是按层扩展：

第 0 层是起点
第 1 层是一步能到的点
第 2 层是两步能到的点

所以第一次到达某个点时，走的步数就是最短步数。

常见写法如下：

vector<vector<int>> g(n);
vector<int> dist(n, -1);
queue<int> q;

dist[start] = 0;
q.push(start);

while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : g[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

这里：

dist[v] == -1 表示没访问过
dist[v] = dist[u] + 1 表示从起点到 v 的最短距离

BFS 最短路适合：

无权图
网格最短步数
每次移动代价相同的问题

3）何时使用优先队列

优先队列主要出现在：

Dijkstra
堆优化搜索
每次都要取当前最小代价状态的问题

什么时候需要优先队列，可以这样判断：

如果当前题目里：

边有权值
而且权值不都相同
需要每次优先扩展“当前距离最小”的状态

那么通常就要考虑优先队列。

简单区分可以记成：

无权图最短路：BFS
非负权图最短路：Dijkstra + 优先队列

也就是说，优先队列的作用是：

帮你快速拿到“当前最优状态”
而不是按普通队列那样先进先出

4. 并查集

1）适用场景

并查集（Disjoint Set Union，DSU）主要用来处理这类问题：

判断两个点是否属于同一个集合
动态合并两个集合
连通性问题
无向图连通块问题
Kruskal 最小生成树

它最适合的题型特征是：

不断给出两点关系
问两个点是否连通
合并若干连通块

并查集的核心操作只有两个：

find(x)：查找 x 所在集合的代表元
union(x, y)：合并 x 和 y 所在的集合

基础写法如下：

vector<int> p(n);

void init() {
    for (int i = 0; i < n; i++) p[i] = i;
}

这里一开始每个点单独成一个集合。

2）路径压缩

路径压缩是并查集最重要的优化之一。

普通 find(x) 可以写成：

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

这里的：

p[x] = find(p[x]);

就是路径压缩。

它的作用是：

在查找根节点的过程中
把沿途所有点都直接挂到根上

这样下次再查时就会更快。

你可以把它理解成：

原来是一条很长的链
查过一次后，直接压扁成“很多点直接指向根”

所以路径压缩能大幅提升效率。

3）按秩合并

按秩合并也是并查集的常见优化。

核心思想是：

合并两个集合时，尽量让“矮的树”挂到“高的树”下面
避免树退化得太深

常见做法是维护：

size[]：集合大小
或 rank[]：树的高度近似值

例如按集合大小合并：

vector<int> p(n), sz(n, 1);

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;

    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}

这里就是让小集合挂到大集合下面。

路径压缩 + 按秩合并之后，并查集的单次操作复杂度可以近似看成：

O(1) 平均非常快
更严格地说是均摊 O(α(n))

这里的 α(n) 是反阿克曼函数，增长极慢，实际中几乎可以视为常数。

5. 拓扑排序

1）入度法

拓扑排序用于处理 有向图中的先后依赖关系。

最经典的方法是入度法，也叫 Kahn 算法。

它的核心思想是：

先找所有入度为 0 的点
这些点说明没有前置依赖，可以先处理
删除这些点后，更新它们邻居的入度
再继续找新的入度为 0 的点

基本写法如下：

vector<vector<int>> g(n);
vector<int> indeg(n, 0);

for (每条边 u -> v) {
    g[u].push_back(v);
    indeg[v]++;
}

queue<int> q;
for (int i = 0; i < n; i++) {
    if (indeg[i] == 0) q.push(i);
}

vector<int> topo;
while (!q.empty()) {
    int u = q.front();
    q.pop();
    topo.push_back(u);

    for (int v : g[u]) {
        indeg[v]--;
        if (indeg[v] == 0) q.push(v);
    }
}

如果最后：

topo.size() == n

说明成功完成拓扑排序。

否则说明图里存在环。

拓扑排序常用于：

课程安排
任务依赖
先修关系
DAG 上的顺序处理

2）有向无环图

拓扑排序只适用于 有向无环图，也就是 DAG（Directed Acyclic Graph）。

原因是：

如果图里有环，那么环上的点互相依赖
就不可能排出一个合法的先后顺序

例如：

A -> B
B -> C
C -> A

这就形成了一个环，谁都不能先做。

所以：

能拓扑排序 <=> 图是 DAG
拓扑排序结果不一定唯一
只要满足所有依赖关系，就是合法结果

在 LeetCode 里，涉及 DAG 的常见题型包括：

课程表
任务调度
依赖关系判断
DAG 上 DP

你可以把拓扑排序记成一句话：

处理有向无环图中的依赖顺序
每次先处理入度为 0 的点

十、回溯与搜索

1. 回溯法

回溯法本质上是一种 在搜索过程中不断尝试、不断撤销选择 的方法。

它通常适用于这类问题：

要求列出所有方案
要求统计所有满足条件的方案数
每一步都有若干种选择
当前选择会影响后续选择

回溯的核心思路可以概括成三步：

做选择
递归进入下一层
撤销选择

常见写法框架如下：

void dfs(...) {
    if (到达终止条件) {
        记录答案;
        return;
    }

    for (每一种选择) {
        做选择;
        dfs(...);
        撤销选择;
    }
}

1）子集

子集问题的特点是：

对每个元素，都有“选”或“不选”两种决定
最终要枚举所有可能的选择结果

例如数组 [1,2,3] 的子集包括：

[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]

子集问题常见写法有两种：

一种是“每个位置选或不选”：

void dfs(int u) {
    if (u == n) {
        ans.push_back(path);
        return;
    }

    dfs(u + 1);

    path.push_back(nums[u]);
    dfs(u + 1);
    path.pop_back();
}

另一种是“枚举当前层从哪个位置开始选”：

void dfs(int start) {
    ans.push_back(path);
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        dfs(i + 1);
        path.pop_back();
    }
}

子集问题的核心在于：

每个元素最多选一次
后面的选择不能回头选前面的元素
通常用 start 控制搜索起点

2）排列

排列问题的特点是：

元素顺序不同，通常算不同答案
每个位置要从“还没用过的元素”里选一个

例如 [1,2,3] 的排列包括：

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

排列问题通常要配合 used[] 数组：

vector<int> path;
vector<bool> used;
vector<vector<int>> ans;

void dfs() {
    if (path.size() == nums.size()) {
        ans.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;

        used[i] = true;
        path.push_back(nums[i]);

        dfs();

        path.pop_back();
        used[i] = false;
    }
}

排列问题的核心在于：

每一层是在决定当前位置放谁
一个元素被选过后不能重复使用
所以通常要记录“哪个元素已经用过了”

3）组合

组合问题的特点是：

从若干元素中选出固定数量
顺序通常不重要

例如从 [1,2,3,4] 中选 2 个，组合有：

[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]

组合问题和子集问题很像，通常也会用 start 控制起点：

void dfs(int start) {
    if (path.size() == k) {
        ans.push_back(path);
        return;
    }

    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        dfs(i + 1);
        path.pop_back();
    }
}

组合问题的关键是：

不能重复选同一个元素
也不能因为顺序不同而重复计数
所以下一层通常从 i + 1 开始搜

4）去重

回溯题里最麻烦的部分之一就是去重。

去重问题通常出现在：

原数组里有重复元素
题目要求结果不能重复

比如：

全排列 II
子集 II
组合总和 II

最常见的做法是：

先排序
在同一层跳过重复元素

典型写法如下：

sort(nums.begin(), nums.end());

for (int i = start; i < nums.size(); i++) {
    if (i > start && nums[i] == nums[i - 1]) continue;

    path.push_back(nums[i]);
    dfs(i + 1);
    path.pop_back();
}

这里的重点是：

i > start
nums[i] == nums[i - 1]

它表示：

同一层里，如果当前元素和前一个元素相同，就跳过，避免生成重复分支。

要特别区分：

同一层去重
同一路径上允许继续往下选

这是很多回溯题最容易写错的地方。

2. DFS

DFS 是 Depth First Search，也就是深度优先搜索。

它的特点是：

一条路尽量走到底
走不通再回退
常常和递归一起使用

DFS 和回溯关系很近。很多回溯题，本质上就是 DFS。
区别在于：

DFS 更强调“搜索过程”
回溯更强调“做选择 + 撤销选择”

1）递归写法

DFS 最常见的写法就是递归。

基本框架如下：

void dfs(状态) {
    if (终止条件) {
        处理答案;
        return;
    }

    for (下一步的选择) {
        dfs(新的状态);
    }
}

例如遍历二叉树：

void dfs(TreeNode* root) {
    if (!root) return;
    dfs(root->left);
    dfs(root->right);
}

例如遍历网格：

void dfs(int x, int y) {
    if (越界或不能走) return;

    vis[x][y] = true;

    for (四个方向) {
        dfs(nx, ny);
    }
}

递归 DFS 的优点是：

写法自然
代码短
很适合树、图、网格、回溯问题

2）状态恢复

状态恢复是 DFS 和回溯题里的关键点。

如果你在递归前修改了某个状态，那么递归返回后，通常要把这个状态恢复回来，否则会影响后续分支。

例如：

path.push_back(nums[i]);
dfs(...);
path.pop_back();

这里的 pop_back() 就是状态恢复。

再比如：

used[i] = true;
dfs();
used[i] = false;

这里把 used[i] 改回 false，也是状态恢复。

你可以把它理解为：

递归前：进入这条分支
递归后：退出这条分支，回到现场

如果状态恢复漏写，常见后果包括：

答案缺失
路径混乱
元素重复使用
后续分支被污染

3）剪枝

剪枝就是：

提前判断某条分支不可能得到合法答案，于是直接不搜了。

它的作用是减少无意义搜索，提高效率。

例如组合总和里，如果当前和已经超过目标值，就没必要继续搜：

if (sum > target) return;

再比如组合问题里，如果剩余元素数量已经不够凑满答案，也可以提前退出。

剪枝常见思路包括：

当前和已经超了
当前长度已经超过限制
剩余元素数量不够
当前状态已经不可能比已有答案更优

剪枝的本质不是改变结果，而是：

减少搜索树中无效的分支。

3. BFS

BFS 是 Breadth First Search，也就是广度优先搜索。

它的特点是：

从起点开始一层一层向外扩展
先搜距离近的状态，再搜距离远的状态
通常借助队列实现

BFS 最经典的应用是：

求最短步数
层序遍历
无权图最短路

1）最短步数

如果图或状态图里每条边的代价都相同，那么 BFS 非常适合求最短步数。

因为 BFS 的搜索顺序天然就是：

先扩展一步能到的状态
再扩展两步能到的状态
再扩展三步能到的状态

所以第一次到达终点时，通常就是最短步数。

典型框架如下：

queue<pair<int, int>> q;
q.push({sx, sy});
vis[sx][sy] = true;

int step = 0;
while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
        auto [x, y] = q.front();
        q.pop();

        if (到达终点) return step;

        for (每个方向) {
            if (合法且未访问) {
                vis[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    step++;
}

这种按层扩展的写法，在“最短步数”题里非常常见。

2）层序扩展

BFS 的另一个典型特征就是“按层搜索”。

最经典的例子是二叉树层序遍历：

queue<TreeNode*> q;
q.push(root);

while (!q.empty()) {
    int sz = q.size();
    vector<int> level;

    while (sz--) {
        TreeNode* node = q.front();
        q.pop();

        level.push_back(node->val);

        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }

    ans.push_back(level);
}

这里每次先记录当前队列大小 sz，就是为了把“同一层”的节点一起处理掉。

所以 BFS 特别适合：

一层一层处理状态
按距离扩展
输出层序结果

3）状态判重

BFS 里状态判重非常重要。

因为 BFS 会不断从当前状态扩展到新状态，如果不判重，就可能：

重复访问同一个状态
队列爆炸
陷入死循环

最常见的做法是用：

vector<vector<bool>> vis
unordered_set
set

来记录某个状态是否访问过。

例如网格中：

vis[x][y] = true;

例如字符串状态中：

unordered_set<string> vis;
if (!vis.count(next)) {
    vis.insert(next);
    q.push(next);
}

状态判重的关键点是：

状态一入队，就标记已访问
不要等出队再标记

因为如果等到出队才标记，同一个状态可能已经被重复入队很多次了。

你可以把 BFS 的核心记成一句话：

用层数表示步数
用队列维护当前层
用判重结构避免重复状态

十一、动态规划

1. 动态规划的基本思路

动态规划（Dynamic Programming，简称 DP）本质上是在解决这类问题：

原问题可以拆成若干个子问题
子问题之间有重复
当前问题的答案可以由更小子问题的答案推出来

所以动态规划的核心不是“背公式”，而是四步：

定义状态
写出转移
设好初始化
确定遍历顺序

1）状态定义

状态定义是动态规划里最重要的一步。

所谓状态，简单理解就是：

dp[i] 或 dp[i][j] 到底表示什么。

如果状态没定义清楚，后面的转移和初始化基本都会乱。

常见状态定义方式有：

dp[i]：表示前 i 个元素的最优解
dp[i]：表示以 i 结尾的最优解
dp[i][j]：表示区间 [i, j] 上的答案
dp[i][j]：表示考虑前 i 个物品、容量为 j 时的最优解
dp[i][j]：表示 s 的前 i 个字符和 t 的前 j 个字符之间的答案

做题时一定要先问自己一句：

这个状态到底描述的是“谁的答案”。

例如：

dp[i] 是“前 i 个元素”的答案
还是“第 i 个位置结尾”的答案

这两个定义可能完全不一样。

2）状态转移

状态转移就是：

当前状态如何由之前的状态推出来。

也就是 DP 的核心递推关系。

例如斐波那契数列：

dp[i] = dp[i - 1] + dp[i - 2];

例如爬楼梯：

dp[i] = dp[i - 1] + dp[i - 2];

例如最大子数组和：

dp[i] = max(nums[i], dp[i - 1] + nums[i]);

写转移时通常要想清楚：

当前这一位选还是不选
从哪个状态转移过来
是否要分类讨论
所有可能情况有没有覆盖完整

转移方程写不对，通常不是“公式记错”，而是：

状态没定义清楚
情况没有分全

3）初始化

初始化就是：

最小子问题的答案是什么。

因为动态规划是从小问题推大问题，所以必须先把“起点”设好。

例如：

dp[0] = 1;
dp[1] = 1;

或者：

dp[0][0] = 0;

或者在背包里：

dp[0][j] = 0;

初始化经常决定整题是否正确。

因为如果起点错了，后面所有转移都会错。

做题时要特别注意：

dp[0] 表示什么
第一行、第一列要不要单独初始化
不合法状态要不要设成负无穷 / 正无穷 / 0

4）遍历顺序

遍历顺序决定了：

你在计算当前状态时，依赖的那些状态是否已经算出来了。

例如线性 DP 通常从前往后：

for (int i = 1; i < n; i++) {
    ...
}

区间 DP 通常按区间长度从小到大枚举：

for (int len = 1; len <= n; len++) {
    ...
}

0/1 背包通常容量要从大到小枚举：

for (int j = m; j >= w[i]; j--) {
    ...
}

完全背包通常容量要从小到大枚举：

for (int j = w[i]; j <= m; j++) {
    ...
}

所以做 DP 时一定要问：

我当前这个状态依赖谁，那我就必须在它后面算。

2. 经典类型

1）线性 DP

线性 DP 是最基础的一类动态规划。

特点是：

状态通常排成一条线
当前状态只依赖前面若干个状态

典型题型包括：

爬楼梯
打家劫舍
最大子数组和
最长递增子序列

常见形式：

dp[i] = ...

例如爬楼梯：

dp[i] = dp[i - 1] + dp[i - 2];

例如打家劫舍：

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);

线性 DP 的关键是看清：

dp[i] 表示什么
当前点和前一个点之间的关系是什么

2）背包问题

背包问题是 DP 里的高频大类。

其核心结构通常是：

有若干个物品
每个物品有体积 / 重量
每个物品有价值
问如何选择使总价值最大，或方案数最多

最经典的是 0/1 背包：

每个物品只能选一次

状态定义常见为：

dp[i][j]

表示：

前 i 个物品
容量为 j
时的最优答案

转移通常是：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

滚动数组优化后常写成：

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

背包问题常见变种有：

0/1 背包
完全背包
多重背包
分组背包
背包求方案数
背包求可行性

做背包时最关键的是：

这是 0/1 还是完全背包
容量的遍历方向对不对

3）区间 DP

区间 DP 适用于：

状态和某一段连续区间有关
当前区间答案由更短区间转移而来

状态通常定义为：

dp[i][j]

表示区间 [i, j] 上的答案。

典型题型包括：

最长回文子序列
石子合并
戳气球
括号匹配类区间问题

区间 DP 的典型思路是：

先枚举区间长度
再枚举左端点
根据更短区间转移到更长区间

典型枚举方式：

for (int len = 1; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        ...
    }
}

区间 DP 的关键是：

当前区间依赖更短区间
所以必须先算短的，再算长的

4）子序列 DP

子序列 DP 通常和两个序列之间的关系有关。

状态经常定义为：

dp[i][j]

表示：

第一个序列前 i 个元素
第二个序列前 j 个元素
的某种最优值

典型题型包括：

最长公共子序列（LCS）
编辑距离
不同的子序列
最长重复子数组
判断子序列

例如最长公共子序列：

if (text1[i - 1] == text2[j - 1])
    dp[i][j] = dp[i - 1][j - 1] + 1;
else
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

这类题的关键在于：

两个指针各走到哪里
当前字符相等时怎么转移
不相等时保留哪种可能

子序列 DP 很容易写成二维 DP。

5）树形 DP

树形 DP 适用于：

问题结构是一棵树
当前节点的答案和子节点有关

其核心思路通常是：

先递归处理子树
再利用子树信息更新当前节点答案

典型题型包括：

树上最大独立集
打家劫舍 III
树的直径
树上选点问题

常见写法是 DFS + DP：

void dfs(int u, int parent) {
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u);
        ...
    }
}

例如树上选点问题，经常会定义：

dp[u][0]：不选 u 时，子树的最优解
dp[u][1]：选 u 时，子树的最优解

树形 DP 的关键是：

明确“当前节点选 / 不选”的状态
明确子节点如何影响父节点

3. 常见坑

1）状态定义不清

这是 DP 最常见的问题。

比如：

dp[i] 到底表示前 i 个元素的答案
还是以 i 结尾的答案

这两个定义不同，转移会完全不同。

所以做 DP 时，第一件事不是急着写公式，而是先把状态说清楚。

2）转移不完整

很多 DP 写错，不是因为不会，而是少考虑了一种情况。

例如：

当前元素选还是不选
当前字符相等还是不相等
当前区间从哪个分割点转移
当前背包是拿还是不拿

只要漏掉一种可能，答案就可能错。

所以写转移时一定要问：

所有情况都覆盖了吗？

3）初始化错误

初始化错是 DP 高频 bug 来源。

常见问题包括：

忘了设 dp[0]
第一行第一列没有单独处理
不合法状态没有设成极小值 / 极大值
默认值和题意不符

尤其是二维 DP，第一行第一列经常要单独想。

4）滚动数组覆盖顺序错

滚动数组优化时，最容易写错的是遍历方向。

例如：

0/1 背包必须从大到小枚举容量
完全背包通常从小到大枚举容量

如果方向错了，就会把“本轮刚更新过的值”拿来重复使用，导致状态含义变掉。

所以滚动数组优化时一定要先确认：

当前状态能不能重复使用同一件物品
遍历方向该往前还是往后

十二、位运算与数学基础

1. 位运算

位运算常见于：

状态压缩
二进制技巧
子集枚举
快速计算
树状数组
数学题和构造题

它的特点是：

运算速度快
写法短
但前提是要真正理解二进制含义

1）与、或、异或

按位与 `&`

按位与的规则是：

两位都为 1，结果才为 1
否则为 0

例如：

5 & 3

二进制下：

5 = 101
3 = 011

所以：

101 & 011 = 001

结果是：

常见用途：

判断某一位是不是 1
取二进制的某些位
lowbit(x) = x & -x

例如判断第 k 位是否为 1：

if (x & (1 << k)) {
    // 第 k 位是 1
}

按位或 `|`

按位或的规则是：

两位只要有一位为 1，结果就是 1

例如：

5 | 3

二进制下：

101 | 011 = 111

结果是：

常见用途：

把某一位置成 1
合并状态

例如把第 k 位置成 1：

x |= (1 << k);

按位异或 `^`

按位异或的规则是：

两位不同，结果为 1
两位相同，结果为 0

例如：

5 ^ 3

二进制下：

101 ^ 011 = 110

结果是：

异或有几个非常重要的性质：

a ^ a = 0
a ^ 0 = a
异或满足交换律和结合律

所以它常用于：

找只出现一次的数
交换两个数
状态翻转

例如把第 k 位翻转：

x ^= (1 << k);

2）移位

移位分为左移和右移。

左移 `<<`

x << k

表示把 x 的二进制整体向左移动 k 位。

通常可以理解为：

x * 2^k

例如：

3 << 2

因为：

3 = 11
左移两位变成 1100

结果是：

常见用途：

快速乘以 2^k
构造掩码
表示某个二进制状态

例如：

1 << k

表示一个只有第 k 位为 1 的数。

右移 `>>`

x >> k

表示把 x 的二进制整体向右移动 k 位。

对于非负整数，通常可以理解为：

x / 2^k

例如：

10 >> 1

因为：

10 = 1010
右移一位变成 101

结果是：

常见用途：

快速除以 2^k
取二进制高位
二分里写成：

int mid = (l + r) >> 1;

3）lowbit

lowbit(x) 表示：

x 的二进制表示中，最低位那个 1 所对应的值。

标准写法是：

int lowbit(int x) {
    return x & -x;
}

例如：

lowbit(6)
6 = 110
结果是 2
lowbit(8)
8 = 1000
结果是 8
lowbit(12)
12 = 1100
结果是 4

lowbit 最经典的用途就是：

树状数组

因为它可以快速找到当前节点管辖区间的长度。

4）常见技巧

判断奇偶

if (x & 1) {
    // 奇数
} else {
    // 偶数
}

因为：

奇数最低位是 1
偶数最低位是 0

取出第 `k` 位

int bit = (x >> k) & 1;

这表示取 x 的第 k 位。

把第 `k` 位置成 `1`

x |= (1 << k);

把第 `k` 位清成 `0`

x &= ~(1 << k);

把第 `k` 位翻转

x ^= (1 << k);

去掉最低位的 `1`

x &= (x - 1);

这个技巧非常经典。

例如：

x = 12 = 1100
x - 1 = 1011
1100 & 1011 = 1000

也就是说，最低位那个 1 被删掉了。

常见用途：

统计二进制中 1 的个数
位运算优化

例如统计 1 的个数：

int cnt = 0;
while (x) {
    x &= (x - 1);
    cnt++;
}

枚举子集

如果一个集合状态写成二进制掩码 mask，那么它的所有子集可以这样枚举：

for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub 是 mask 的一个非空子集
}

这在状态压缩 DP 和组合枚举里很常见。

2. 数学专题

数学基础在 LeetCode 中很常见，尤其是：

数论题
组合计数题
快速计算题
取模题
概率 / 方案数题

1）最大公约数 / 最小公倍数

最大公约数 GCD

最大公约数（Greatest Common Divisor）表示：

两个整数共同的最大因数。

例如：

gcd(12, 18) = 6

最经典的写法是欧几里得算法：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

例如：

gcd(18, 12)
= gcd(12, 6)
= gcd(6, 0)
= 6

常见用途：

约分
判断互质
数组公因子问题
分数 / 比例题

最小公倍数 LCM

最小公倍数（Least Common Multiple）表示：

两个整数共同的最小正倍数。

公式是：

lcm(a, b) = a / gcd(a, b) * b

代码写法：

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

这里先除后乘，是为了减少溢出风险。

2）快速幂

快速幂用于高效计算：

a^b
a^b mod m

因为普通连乘要做 b 次，复杂度是 O(b)。

快速幂利用二进制拆分指数，把复杂度降到：

O(log b)

不取模版本

long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

取模版本

long long qpow(long long a, long long b, long long mod) {
    long long res = 1 % mod;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

快速幂的核心思想是：

如果当前二进制位是 1，就把当前底数乘进答案
每轮把底数平方
指数右移一位

常见用途：

大数幂取模
组合数取模
逆元
矩阵快速幂的基础思想

3）质数筛

质数筛用于快速求出：

1 ~ n 中哪些数是质数
质数个数
最小质因子等

最常见的是埃氏筛。

埃氏筛

vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}

核心思想是：

如果 i 是质数
那么它的倍数一定不是质数
把这些倍数筛掉

复杂度通常记为：

O(n log log n)

线性筛

如果你想进一步优化，也可以用线性筛。

它的特点是：

每个合数只被最小质因子筛掉一次
复杂度是 O(n)

基础写法：

vector<int> primes;
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;for (int i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push_back(i);
    for (int p : primes) {
        if (i * p > n) break;
        isPrime[i * p] = false;
        if (i % p == 0) break;
    }
}

刷题里如果只是普通筛质数，埃氏筛通常已经够用了。

4）组合数

组合数表示：

从 n 个元素中选 k 个元素的方案数。

记作：

C(n, k)
或 \binom{n}{k}

公式是：

C(n, k) = n! / (k! * (n - k)!)

但在编程里，直接用阶乘公式往往会：

溢出
不方便取模

所以常见做法有几种。

杨辉三角递推

利用公式：

C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

可以预处理组合数表：

vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
for (int i = 0; i <= n; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) {
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
}

适合：

n 不大
多次查询组合数

阶乘 + 逆元

如果题目要求：

C(n, k) mod p
且 n 很大
查询很多次

通常会预处理：

阶乘 fac[i]
阶乘逆元 invfac[i]

然后用公式快速求：

C(n, k) = fac[n] * invfac[k] % mod * invfac[n - k] % mod

这里逆元常用快速幂求。

常见性质

组合数有几个常见性质：

C(n, 0) = 1
C(n, n) = 1
C(n, k) = C(n, n-k)

最后这个对优化很常用，因为可以把较大的 k 变小。

十三、LeetCode 高频易错点速记

1. 二分查找

1）死循环

2）边界错

3）`mid` 偏向错误

2. 前缀和

1）下标偏移

2）公式写错

3. STL

1）默认行为没搞清

2）复杂度误判

3）迭代器失效

4. 线段树

1）边界错

2）更新后忘维护

3）懒标记漏传

十四、题型到工具的映射

1. 看到这些题先想到 `unordered_map`

两数之和
前缀和计数
频次统计
快速查找

2. 看到这些题先想到 `set / map`

需要自动排序
查找前驱后继
区间边界问题

3. 看到这些题先想到 `priority_queue`

Top K
动态维护最值
贪心
最短路

4. 看到这些题先想到前缀和

区间和
子数组和
快速统计连续区间

5. 看到这些题先想到线段树

区间查询 + 动态更新
维护区间最值
查询某个区间的第一个满足条件的位置

一、C++ 与 STL 基础

1. std::string

1）它是什么

2）常用方法

3）时间复杂度

4）适用场景

5）常见坑

substr(pos, len) 的第二个参数是长度，不是结束下标

find() 找不到时返回 string::npos

operator[] 不检查越界

字符和字符串不要混淆

在循环中修改字符串时要小心下标变化

size() 返回的是无符号类型

2. std::vector

1）它是什么

2）底层实现

3）常用方法

4）时间复杂度

5）适用场景

6）常见坑

vector 扩容后，原有迭代器、指针、引用可能失效

erase() 删除元素后，后面的元素会前移

insert() 和 erase() 都可能是线性复杂度

clear() 清空的是元素，不一定释放容量

reserve() 只改容量，不改元素个数

resize() 会真的改变元素个数

operator[] 不检查越界

倒序遍历时要注意 size() 是无符号类型

3. std::deque

1）它是什么

2）底层实现

3）常用方法

4）时间复杂度

5）适用场景

6）常见坑

deque 虽然支持随机访问，但底层不是普通连续数组

deque 的中间插入和删除仍然是线性复杂度

operator[] 不检查越界

在循环中删除元素时要注意迭代器失效

deque 不要和 queue 混淆

不是所有需要“队列”的题都必须手写 deque

4. std::list

1）它是什么

2）底层实现

3）常用方法

4）时间复杂度

5）适用场景

6）常见坑

list 不支持按下标随机访问

查找慢，不要因为插删快就误以为它整体都快

sort() 不能写成通用算法的 sort(lst.begin(), lst.end())

unique() 只会删除连续重复元素

remove(x) 和算法里的 remove 不是一回事

list 的内存开销通常比 vector 更大

5. std::set / std::multiset

1）它们是什么

2）底层实现

3）常用方法

4）时间复杂度

5）适用场景

6）常见坑

set 和 multiset 不支持下标访问

它们的迭代器不是随机访问迭代器

set 不允许重复，multiset 允许重复

multiset.erase(x) 会删掉所有值等于 x 的元素

set.erase(x) 和 set.erase(it) 的含义不同

count() 在 set 里不是“统计很多个”

lower_bound() 和 upper_bound() 容易记混

unordered_set 更快，但不能替代所有 set

想取最大值、最小值时不要忘了迭代器写法

6. std::map / std::multimap

1）它们是什么

2）底层实现

3）常用方法

4）时间复杂度

5）适用场景

6）常见坑

map 和 multimap 不支持下标随机访问

map[key] 会在 key 不存在时插入默认值

multimap 没有 operator[]

1. `std::string`

`substr(pos, len)` 的第二个参数是长度，不是结束下标

`find()` 找不到时返回 `string::npos`

`operator[]` 不检查越界

`size()` 返回的是无符号类型

2. `std::vector`

`vector` 扩容后，原有迭代器、指针、引用可能失效

`erase()` 删除元素后，后面的元素会前移

`insert()` 和 `erase()` 都可能是线性复杂度

`clear()` 清空的是元素，不一定释放容量

`reserve()` 只改容量，不改元素个数

`resize()` 会真的改变元素个数

`operator[]` 不检查越界

倒序遍历时要注意 `size()` 是无符号类型

3. `std::deque`

`deque` 虽然支持随机访问，但底层不是普通连续数组

`deque` 的中间插入和删除仍然是线性复杂度

`operator[]` 不检查越界

`deque` 不要和 `queue` 混淆

不是所有需要“队列”的题都必须手写 `deque`

4. `std::list`

`list` 不支持按下标随机访问

`sort()` 不能写成通用算法的 `sort(lst.begin(), lst.end())`

`unique()` 只会删除连续重复元素

`remove(x)` 和算法里的 `remove` 不是一回事

`list` 的内存开销通常比 `vector` 更大

5. `std::set` / `std::multiset`

`set` 和 `multiset` 不支持下标访问

`set` 不允许重复，`multiset` 允许重复

`multiset.erase(x)` 会删掉所有值等于 `x` 的元素

`set.erase(x)` 和 `set.erase(it)` 的含义不同

`count()` 在 `set` 里不是“统计很多个”

`lower_bound()` 和 `upper_bound()` 容易记混

`unordered_set` 更快，但不能替代所有 `set`

6. `std::map` / `std::multimap`

`map` 和 `multimap` 不支持下标随机访问

`map[key]` 会在 key 不存在时插入默认值

`multimap` 没有 `operator[]`

`map::insert()` 遇到重复 key 时不会覆盖旧值

`multimap.erase(key)` 会删掉所有该 key 的元素

`lower_bound()` 和 `upper_bound()` 容易记混

遍历 `map` 时拿到的是键值对，不是单个值

`unordered_map` 更快，但不能替代所有 `map`

`map` 中 key 默认按升序排列，不是按插入顺序

7. `std::unordered_set`

`unordered_set` 是无序的

它不支持 `lower_bound()`、`upper_bound()` 这类有序操作

`count()` 的结果只可能是 `0` 或 `1`

`erase(x)` 和 `erase(it)` 含义不同

平均 `O(1)` 不等于绝对比 `set` 更好

`reserve()` 和 `rehash()` 是优化，不是必须会用

8. `std::unordered_map`

`unordered_map` 是无序的

`mp[key]` 在 key 不存在时会插入默认值

`count()` 的结果只可能是 `0` 或 `1`

`at()` 和 `operator[]` 的行为不同

平均 `O(1)` 不等于一定比 `map` 更好

`reserve()` 和 `rehash()` 是优化，不是必须会用

9. `std::stack`

10. `std::queue`

11. `std::priority_queue`

`priority_queue` 默认是大顶堆

`greater<int>` 写出来的是小顶堆，不要记反

存 `pair` 时，默认比较规则要清楚

`push()` 和 `emplace()` 复杂度同阶，但 `emplace()` 更适合原地构造对象

1）排序：`sort`、`reverse`

2）二分：`lower_bound`、`upper_bound`、`binary_search`

3）去重：`unique`