面向做题，包括系统复习和 HOT100，用于快速回看、防止遗忘。
暂时使用 C++，Python 写法后续系统学习整理。

数组、双指针与滑动窗口

左右指针

双指针常见于有序数组、回文串、区间收缩类问题。常见写法是 left = 0, right = n - 1，从两端向中间逼近。

n 数之和

  • 两数之和如果数组有序，可以排序后用左右指针。
  • 三数之和的核心是固定第一个数，再在后面区间做两数之和。
  • 去重是重点，尤其是三数之和中第一个数不能重复。

有序数组的平方

有序数组可能同时含负数和正数，平方后最大值只会出现在两端。用两个指针分别指向首尾，把较大的平方值从后往前填入答案数组即可。

回文串

最长回文子串常用中心扩展法。枚举每个位置作为中心，分别向两边扩展。

1
2
3
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

二分查找

数组有序时优先考虑二分。推荐统一使用左闭右开区间 [left, right)：

  • while (left < right)：当 left == right 时区间为空。
  • nums[mid] < target 时，left = mid + 1。
  • nums[mid] > target 时，right = mid。
1
2
3
4
5
6
7
8
9
10
int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return -1;
}

颜色分类

荷兰国旗问题的经典做法是三指针：

  • left 表示下一个 0 应放的位置。
  • right 表示下一个 2 应放的位置。
  • i 扫描当前元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
void sortColors(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int i = 0;
    while (i <= right) {
        if (nums[i] == 0) {
            swap(nums[left++], nums[i++]);
        } else if (nums[i] == 2) {
            swap(nums[right--], nums[i]);
        } else {
            i++;
        }
    }
}

快慢指针

快慢指针适合处理原地删除、去重、移动元素等问题。一个指针负责扫描，一个指针负责写入答案区间。

1
2
3
4
5
6
7
8
int slow = 0, fast = 0;
while (fast < nums.size()) {
    if (nums[fast] != nums[slow]) {
        slow++;
        nums[slow] = nums[fast];
    }
    fast++;
}

典型题：

  • 283. 移动零
  • 删除有序数组中的重复项
  • 链表判环、找中点

滑动窗口

滑动窗口本质上也是双指针，只不过维护的是一个动态区间 [left, right)。

核心先想清楚两个问题：

  1. 什么时候扩张窗口？
  2. 什么时候收缩窗口？

求最长

不断加入右边界，当窗口不合法时收缩左边界；窗口重新合法后更新答案。

1
2
3
4
5
6
7
8
9
10
11
for (int right = 0; right < n; ) {
    window[s[right]]++;
    right++;

    while (window[s[right - 1]] > 1) {
        window[s[left]]--;
        left++;
    }

    ans = max(ans, right - left);
}

典型题：

  • 3. 无重复字符的最长子串

求最短

不断加入右边界，只要窗口满足条件，就尝试收缩左边界，在收缩过程中更新最短答案。

1
2
3
4
5
6
7
for (int right = 0; right < n; ) {
    sum += nums[right++];
    while (sum >= target) {
        ans = min(ans, right - left);
        sum -= nums[left++];
    }
}

典型题：

  • 76. 最小覆盖子串
  • 长度最小的子数组

计数类

如果要求“以某个右端点结尾、满足条件的子数组个数”，通常在每次得到合法窗口后累加 right - left。

需要注意：如果数组里有负数，窗口不具备单调性，就不能直接用滑动窗口。例如：

  • 560. 和为 K 的子数组

这类题更适合用前缀和 + 哈希表。

哈希表与字符串

哈希表

哈希表擅长做三件事：

  • 快速查找
  • 计数
  • 去重
1
2
3
4
5
6
7
8
unordered_map<string, int> m;
m["apple"] = 1;
if (m.count("apple")) {
    cout << m["apple"] << endl;
}

unordered_set<int> s;
vector<int> nums(s.begin(), s.end());

典型题

1. 两数之和

维护 值 -> 下标 的映射。遍历到当前位置时，查找 target - nums[i] 是否已经出现过。

202. 快乐数

如果一个数不断替换为“各位平方和”后进入循环，说明不会到达 1。判断是否重复出现，最适合用哈希集合。

454. 四数相加 II

先统计 A + B 的所有和及其出现次数，再枚举 C + D，查找目标补数。

49. 字母异位词分组

把排序后的字符串作为 key 分组。

128. 最长连续序列

把所有数放入哈希集合。只有当前数字的前驱 num - 1 不存在时，才从它开始向后扩展统计连续长度。

注意遍历集合而不是原数组，避免重复元素影响复杂度。

字符串

字符串题最常见的几种思路：

  • 双指针
  • 滑动窗口
  • 哈希计数
  • KMP
1
2
3
4
5
6
7
string s;
reverse(s.begin(), s.end());
int num = stoi(s);
string t = to_string(num);
isdigit(c);
isalnum(c);
isalpha(c);

常见技巧

151. 翻转字符串里的单词

可以用 stringstream 按单词切分。

1
2
3
4
5
stringstream ss(s);
string word;
while (ss >> word) {
    // 处理单词
}

实现 strStr()

进阶做法是 KMP。核心是提前计算模式串的前缀函数，避免主串指针回退。

459. 重复的子字符串

可以结合 KMP 的 next 数组，判断整个串是否由某个更短的子串重复构成。

回溯与 DFS

回溯的本质是暴力穷举，但要通过剪枝减少无效搜索。通常可以把问题抽象成一棵“选择树”：

  • 递归负责纵向遍历
  • for 循环负责横向枚举选择

适用场景：

  • 组合问题
  • 切割问题
  • 子集问题
  • 排列问题
  • 棋盘问题，如 N 皇后、数独

通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void backtracking(路径, 选择列表) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择 in 选择列表) {
        if (不合法) continue;

        做选择;
        backtracking(路径, 选择列表);
        撤销选择;
    }
}

排列、组合、子集

这三类题的区别主要体现在“能不能重复使用元素”和“是否关心顺序”。

常用去重手段：

  • used 数组：适合排列问题
  • startIndex：适合组合和子集问题
  • 先排序，再跳过同层重复元素

子集 II

[1,2,2] 这类有重复元素的输入，要先排序，再保证“同一树层相同元素只使用一次”。

全排列 II

也是先排序，然后跳过同层值相同的分支，避免重复排列。

数独与 N 皇后

这类题本质上是在二维网格上做穷举和约束判断。

  • 数独：每个位置尝试填 1~9，并满足行、列、九宫格合法。
  • N 皇后：每一行尝试放一个皇后，并满足列与对角线合法。

写这类题时，重点是把“合法性判断”和“撤销选择”处理干净。

二叉树

二叉树题可以分成两种思维方式：

  1. 遍历一遍树，在遍历过程中收集信息并更新答案。
  2. 定义递归函数，让左右子树先给出答案，再组合出当前节点的答案。

第二种思路其实和 DP 很像，本质上是“先解决子问题，再得到原问题”。

三种遍历位置

前中后序不是三个固定模板，而是三个“处理节点的时机”：

  • 前序：刚进入节点时
  • 中序：左子树处理完、右子树开始前
  • 后序：即将离开节点时

后序最强，因为它既能拿到当前节点参数，也能拿到左右子树返回值。

典型题

111. 二叉树的最小深度

前序进入节点时维护深度，遇到叶子节点时更新答案，后序离开节点时恢复现场。

101. 对称二叉树

把“判断一棵树是否对称”转化成“判断两棵树是否互为镜像”。

110. 平衡二叉树

一次后序遍历同时得到高度和是否失衡：

  • 返回值 >= 0 表示子树高度
  • 返回值 -1 表示子树已经不平衡，可以直接向上短路

层序遍历

层序遍历适合解决“按层处理”“最短步数”“深度统计”类问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;

    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        for (int i = 0; i < size; i++) {
            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);
        }
        res.push_back(level);
    }
    return res;
}

典型题：

  • 层序遍历
  • 右视图
  • 116. 填充每个节点的下一个右侧节点指针

三种经典算法视角

  • 动态规划关注整棵“子树”如何返回答案。
  • 回溯关注节点间“树枝”的选择。
  • DFS 更关注单个节点的访问和扩展。

动态规划

动态规划的关键不是背公式，而是想清楚下面四件事：

  1. 状态是什么
  2. 选择是什么
  3. dp 数组或函数的定义是什么
  4. 状态转移怎么写
1
2
3
4
5
6
dp[0][0][...] = base case

def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        result = 求最值(result, dp(新状态1, 新状态2, ...))
    return result

上面是自顶向下的写法，也可以写成自底向上的迭代形式。

一个常见误区

“选或不选当前元素”适合子序列问题，比如 0-1 背包。

但子数组问题要求连续，通常不能直接套这个思路。例如最大子数组和，更适合考虑“要不要和前面的结果拼接”。

子序列问题

一维 DP

dp[i] 往往表示“以 nums[i] 结尾”的最优值。

例如：

  • 300. 最长递增子序列

dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。

二维 DP

常见于两个字符串或区间 DP：

  • dp[i][j] 表示 arr1[0..i] 与 arr2[0..j] 的答案
  • 或 dp[i][j] 表示区间 array[i..j] 上的答案

打家劫舍

定义：

  • dp[i] 表示考虑下标 i 及之前所有房屋时，最多能偷到多少钱

转移：

  • 偷第 i 间：dp[i - 2] + nums[i]
  • 不偷第 i 间：dp[i - 1]

所以：

1
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

注意 dp[i - 1] 表示“考虑到第 i - 1 间”的最优解，不代表一定偷了第 i - 1 间。

背包问题

背包问题的两个核心状态通常是：

  • 当前考虑到第几个物品
  • 当前背包容量是多少

定义：

  • dp[i][j] 表示从下标 [0..i] 的物品里任选，装入容量为 j 的背包，最大价值是多少

01 背包的选择是“放”或“不放”。

高频题速查

最后把常见高频题按专题再过一遍，面试前可以直接扫这个列表。

哈希

  • 1. 两数之和
  • 49. 字母异位词分组
  • 128. 最长连续序列

双指针

  • 11. 盛最多水的容器
  • 15. 三数之和
  • 42. 接雨水
  • 283. 移动零

滑动窗口

  • 3. 无重复字符的最长子串
  • 438. 找到字符串中所有字母异位词
  • 76. 最小覆盖子串

前缀和 / 子数组

  • 560. 和为 K 的子数组
  • 53. 最大子数组和

栈和队列

  • 239. 滑动窗口最大值
  • 496. 下一个更大元素 I
  • 739. 每日温度

区间

  • 56. 合并区间

复习的时候建议不要只背题解，而是优先问自己：

  1. 这是哪一类模型？
  2. 状态、指针、窗口分别表示什么？
  3. 为什么这样定义能保证不重不漏？
  4. 有没有更适合的模板可以复用？

只要模型感建立起来，很多题都会从“记答案”变成“现场推出来”。