经典基础

Created2026-03-17Updated2026-03-17

一、核心易错点

1. 数组与越界

  • 循环变量和分类下标分离：不要用外层 i 直接访问固定小数组。
  • 容器访问前先判空或判长度：
1
2
if (!v.empty()) use(v[0]);
if (v.size() > 1) use(v[1]);

2. 输入输出

  • cin >> n 后接 getline，必须先吃掉换行符：
1
2
cin >> n;
cin.ignore();
  • 大数据 I/O 优化：
1
2
ios::sync_with_stdio(0);
cin.tie(0);
  • 固定宽度补零：printf("%05d\n", num)。
  • 输出优先 \n，避免频繁 endl。

3. 数据结构选择

  • 键可能重复时，不用 map 存主体数据（会覆盖），用 struct + vector + sort。
  • 不要求有序时优先 unordered_map/unordered_set。
  • 小范围计数（如 26 字母）优先数组。

4. 边界条件

  • 重点检查：0、空输入、区间端点、整除（余数为 0）。
  • 转换类题目做“正向 + 逆向”自检。

5. 算法策略

  • 能数组模拟就别硬改指针（如链表题可先按地址收集再处理）。
  • 位数少可枚举，位数大用 DFS + 剪枝。

二、字符串输入与分词

1. 按空白读取到 EOF

1
2
3
4
string word;
while (cin >> word) {
    words.push_back(word);
}

2. 读取整行后按空格切词

1
2
3
4
5
6
7
string line;
getline(cin, line);
istringstream iss(line);
string word;
while (iss >> word) {
    words.push_back(word);
}

3. cin >> n 与 getline 混用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
cin >> n;
cin.ignore();

for (int i = 0; i < n; i++) {
    string line;
    if (!getline(cin, line)) break;
    istringstream iss(line);
    string word;
    while (iss >> word) {
        cout << word << ' ';
    }
    cout << '\n';
}

三、排序与比较器

1. sort + Lambda

1
2
3
sort(a.begin(), a.end(), [](const Node& x, const Node& y) {
    return x.key < y.key;
});

2. 结构体内重载 <

1
2
3
4
5
6
7
8
9
10
struct Student {
    int num, de, cai;
    bool operator<(const Student& b) const {
        if (de + cai == b.de + b.cai) {
            if (de == b.de) return num < b.num;
            return de > b.de;
        }
        return de + cai > b.de + b.cai;
    }
};
  • 成员版 operator< 只写一个参数（右操作数）。
  • 建议加 const，保证比较不改对象。

四、map<int, bool> 常用写法

1. 插入/修改

1
2
3
mp[10] = true;
mp.insert({30, true});
mp.emplace(50, false);

2. 遍历（推荐写法）

1
2
3
for (const auto& [key, val] : mp) {
    cout << key << ' ' << boolalpha << val << '\n';
}

五、区间与迭代器

1. begin() 与 end()

  • begin() 指向第一个元素。
  • end() 指向末尾后一个位置，不可解引用。

2. reverse 左闭右开

  • reverse(first, last) 作用区间是 $[first, last)$。
  • 示例：
1
2
reverse(v.begin(), v.begin() + 3); // 前 3 个
reverse(v.begin() + 1, v.end());   // 从第 2 个到末尾

六、格式化输出

1
cout << fixed << setprecision(n) << x << '\n';
  • fixed：固定小数格式。
  • setprecision(n)：配合 fixed 时表示小数位数。

七、sort() 越界保护

1. 推荐：min 限制右边界

1
2
int end_idx = min(i + step, (int)a.size());
sort(a.begin() + i, a.begin() + end_idx);

2. 与 end() 比较

1
2
auto it_end = (a.begin() + i + step > a.end()) ? a.end() : a.begin() + i + step;
sort(a.begin() + i, it_end);

八、工程化小习惯

  • 比较前先判长度，不等直接返回。
  • vector 返回值可直接 return {a, b};。
  • 累加场景优先检查是否误写 =（应为 +=）。

这是一个为你整理的 C++ STL 关联容器与哈希表核心用法总结表。在刷题和面试时，你可以直接在脑海中调出这张表格，快速决定使用哪种数据结构。

九、C++ STL 核心容器对比与速查表

操作大类 具体方法 / 代码片段 适用容器 时间复杂度 (哈希表 / 红黑树) 核心说明与避坑指南
插入 / 修改 insert(val) 全部适用 $O(1)$ / $O(\log n)$ 插入元素。如果 Key 已经存在，则不会覆盖，插入失败。
emplace(args...) 全部适用 $O(1)$ / $O(\log n)$ 原地构造元素，省去拷贝/移动开销，性能通常优于 insert。
container[key] = val 仅 map, unordered_map $O(1)$ / $O(\log n)$ 最常用。Key 存在则修改 Value；Key 不存在则创建并赋默认值。
查找 / 访问 find(key) 全部适用 $O(1)$ / $O(\log n)$ 查找 Key。找到返回对应迭代器，没找到返回 container.end()。
count(key) 全部适用 $O(1)$ / $O(\log n)$ 返回 Key 的数量。在不允许重复的容器中，只能返回 1 或 0（常用于判断存在性）。
at(key) 仅 map, unordered_map $O(1)$ / $O(\log n)$ 访问对应 Key 的 Value。如果 Key 不存在，会抛出越界异常，比 [] 更安全。
lower_bound(key) 仅 set, map (有序) $O(\log n)$ 返回指向第一个 大于或等于 key 的迭代器。哈希表不支持。
upper_bound(key) 仅 set, map (有序) $O(\log n)$ 返回指向第一个 严格大于 key 的迭代器。哈希表不支持。
删除 erase(key) 全部适用 $O(1)$ / $O(\log n)$ 直接根据 Key 删除元素。返回被删除元素的个数（0 或 1）。
erase(iterator) 全部适用 摊还 $O(1)$ 删除迭代器指向的元素（常用于遍历时按条件删除）。
clear() 全部适用 $O(n)$ 清空容器中的所有元素。
容量 / 状态 empty() 全部适用 $O(1)$ 检查容器是否为空。返回 true 或 false。
size() 全部适用 $O(1)$ 返回当前容器中元素的个数。

核心操作速记 (适用于以上所有 STL 容器)

  • 查找是否存在： 首选：if (container.find(key) != container.end())
    • 次选（仅限 set/map）：if (container.count(key) > 0)
  • 插入元素：
    • set / unordered_set: insert(key)
    • map / unordered_map: container[key] = value (最方便) 或 insert({key, value})
  • 删除元素：
    • 按值删除：erase(key)
  • 遍历容器：
    • C++11 写法：for (auto it : container)
    • C++17 结构化绑定 (针对 map)：for (auto [key, value] : my_map)

十、算法题型强化（从 N 数之和开始）

这一部分按“题型框架 -> 高频坑点 -> 可复用模板思维”整理，便于刷题时快速调用。

1. N 数之和家族（3Sum / 4Sum）

题型总框架

  • 先排序，再做枚举 + 双指针。
  • 去重必须发生在遍历过程中，而不是预处理阶段。
  • 4Sum 及以上场景优先考虑剪枝，否则容易超时。

四个高频坑点

  1. 不能提前去重
  • 不要先用 set 对原数组去重。
  • 原数组中的重复值可能是合法答案的一部分，例如 [0, 0, 0]。
  1. 去重边界要写准
  • 外层去重：if (k > 0 && nums[k] == nums[k - 1]) continue;
  • 内层去重：if (i > k + 1 && nums[i] == nums[i - 1]) continue;
  • 关键点：内层必须和当前层起点比较，不能写成 i > 0。
  1. 警惕整型溢出
  • 多个 int 累加时可能溢出。
  • 计算和时先提升类型：(long long)nums[k] + nums[i] + ...。
  1. 剪枝时分清 break 与 continue
  • 最小和已经大于 target：后续只会更大，直接 break。
  • 最大和仍小于 target：当前值太小，应该 continue。

2. 回溯算法（Backtracking）

统一骨架

终止条件 -> 做选择 -> 递归 -> 撤销选择。

两种写法对比

  1. 值传递写法（易写易懂）
  • 形式：void backtrack(int n, string path)
  • 递归：backtrack(n, path + ch)
  • 特点：天然不需要手动撤销，代码直观。
  • 代价：频繁拷贝字符串，适合 $n$ 很小（如 $n \le 10$）。
  1. 引用传递写法（面试主流）
  • 形式：void backtrack(int n, string& path)
  • 必须严格遵循：加入字符 -> 递归 -> pop_back()。
  • 特点：性能更好，适合规模更大的搜索。

3. 哈希表优化思路

思路一：分组哈希（降维）

  • 典型题：四数相加 II（四个独立数组）。
  • 做法：前两数组求和计数，后两数组查补数 0 - c - d。
  • 复杂度从 $O(n^4)$ 降为 $O(n^2)$。

思路二：能用定长数组就别用哈希

  • 当键空间很小且固定（如 26 个小写字母）时，优先 int hash[26] = {0};。
  • 数组访问常数更小、内存连续、实现也更稳定。

4. 一页速记（实战决策）

  • N 数之和：排序 + 双指针 + 分层去重 + 剪枝。
  • 回溯：小规模可值传递，大规模用引用传递并手动撤销。
  • 哈希优化：先看能否分组降维，再看能否降到定长数组。