C++刷 LeetCode Hot100 笔记（四）双指针、滑动窗口、前缀和入门
1. 这一篇开始接触真正的做题思路
从这一篇开始，重点不只是语法了，而是：
-
看到题目，知道往哪个方向想
-
知道什么时候该用双指针
-
知道什么时候该用滑动窗口
-
知道什么时候该用前缀和
这三个东西在 Hot100 里面非常常见，而且很多数组题、字符串题，背后其实就是它们。
现在先不用追求“一眼秒题”，先做到：
看到题目时，脑子里能冒出来几个常见套路。
这就已经很不错了。
2. 先说结论：这三个东西分别是干什么的
2.1 双指针
一般用于：
-
从两边往中间逼近
-
同一个数组里两个位置一起移动
-
快慢指针
-
原地修改数组
-
有序数组找答案
你可以把它理解成：
不用一个指针傻傻地一个一个试，而是两个位置配合着走。
2.2 滑动窗口
一般用于：
-
连续子数组
-
连续子串
-
求最长、最短
-
满足某种条件的区间
你可以把它理解成：
维护一个会移动的区间。
比如 [left, right] 这一段就是当前窗口。
2.3 前缀和
一般用于：
-
快速求一段区间的和
-
子数组和问题
-
和为 k 的子数组
-
连续区间统计
你可以把它理解成：
提前把前面累加好，后面查区间和就快了。
3. 双指针到底是什么
双指针，说白了就是：
同时用两个下标来做题。
比如：
int left = 0;
int right = nums.size() - 1;
或者：
int slow = 0;
int fast = 0;
虽然都叫双指针，但其实常见的有两类。
4. 双指针的两种最常见写法
4.1 左右指针
这种一般是：
-
一个在最左边
-
一个在最右边
-
两边往中间靠
模板长这样：
int left = 0;
int right = nums.size() - 1;
while (left < right) {
// 根据条件处理
if (某种情况) {
left++;
} else {
right--;
}
}
典型题：
-
两数之和 II（有序数组）
-
盛最多水的容器
-
三数之和里的内部双指针
-
回文串判断
4.2 快慢指针
这种一般是：
-
fast负责往前找 -
slow负责维护答案位置
模板长这样：
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (满足条件) {
nums[slow] = nums[fast];
slow++;
}
}
典型题：
-
删除有序数组中的重复项
-
移动零
-
原地删除元素
-
链表找中点
-
链表判环
5. 什么题该想到双指针
你可以先记这几个信号。
信号 1：题目要求原地修改数组
比如：
-
把 0 移到最后
-
删除某些元素
-
去重
这时候经常是快慢指针。
信号 2：题目跟“有序数组”有关
比如：
-
找两个数之和
-
去重
-
三数之和
这时候很可能是左右指针。
信号 3：题目让你从两端往中间判断
比如：
-
回文串
-
盛最多水的容器
这时候一般就是左右指针。
6. 先看第一道经典题：移动零
题目大意：
给你一个数组 nums，把所有 0 移到末尾，同时保持非零元素的相对顺序。
比如：
[0,1,0,3,12]
变成：
[1,3,12,0,0]
6.1 这题为什么想到快慢指针
因为这题本质上是：
-
fast负责遍历整个数组 -
遇到非零元素，就放到前面去
-
slow负责记录“前面该放到哪”
也就是：
fast 找有效值，slow 放有效值。
6.2 做法
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
}
}
};
6.3 这段代码怎么理解
以：
[0,1,0,3,12]
为例。
一开始：
-
slow = 0 -
fast从左往右扫
过程：
-
fast = 0，是 0，不处理 -
fast = 1，是 1，和nums[slow]交换 -
然后
slow++ -
后面继续找非零元素往前放
你可以把前面的区间理解成：
[0, slow-1] 这一段，始终都是处理好的非零区。
这个想法特别重要。
6.4 这题你要学到什么
不是死记这道题，而是学这个模型：
快慢指针常见模型
-
fast负责扫描 -
slow负责放答案 -
前面一段区域始终保持“已经处理好”
这个模型后面你会反复见到。
7. 第二道经典题：盛最多水的容器
题目大意：
给你一个数组 height，每个位置是一根柱子的高度。
任选两根柱子，和 x 轴组成一个容器，问最多能装多少水。
7.1 暴力为什么不行
最直接想法是：
-
枚举左边一根柱子
-
再枚举右边一根柱子
-
算面积
-
取最大值
这就是两层循环，复杂度 O(n^2)。
数据一大就不行。
7.2 这题为什么想到左右指针
因为容器面积公式是：
面积 = 宽度 * 高度较小值
也就是：
(right - left) * min(height[left], height[right])
这里有个很关键的点：
真正卡面积上限的，是短板。
也就是左右两根柱子里，更矮的那一根。
所以如果当前：
-
左边矮，右边高
那你把右边往左移，宽度变小了，但短板可能还是左边，没什么意义。
真正有希望变大的，是：
移动更矮的那一边。
这个就是这题最核心的思路。
7.3 代码
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int ans = 0;
while (left < right) {
int area = (right - left) * min(height[left], height[right]);
ans = max(ans, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ans;
}
};
7.4 这题你要学到什么
这题不是“左右夹一下”这么简单，而是你要学会这个判断逻辑：
左右指针常见核心：
-
当前答案由左右两边共同决定
-
每次只移动一个指针
-
移动哪一个，不是乱动
-
一般移动“更不可能带来更优答案”的那个，或者移动“限制答案的那个”
在这题里，就是移动短板。
8. 三数之和为什么也常用双指针
Hot100 里还有一道非常经典的题：三数之和。
这题的大方向是：
-
先排序
-
固定一个数
-
剩下两个数用双指针找
形式大概是：
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
// 根据 sum 和 0 的关系移动指针
}
}
你现在不用急着把这题完全吃透，但你先记住：
排序 + 双指针 是 Hot100 里特别经典的一组搭配。
9. 滑动窗口到底是什么
滑动窗口本质上还是双指针，只不过它更强调：
维护一个连续区间。
一般写成：
int left = 0;
for (int right = 0; right < n; right++) {
// 把 nums[right] 加入窗口
while (窗口不满足条件) {
// 缩小左边
left++;
}
// 更新答案
}
这里的窗口就是：
[left, right]
你可以把它想成一个会伸缩的框。
-
right往右走：窗口变大 -
left往右走：窗口变小
10. 什么题该想到滑动窗口
你先记几个关键词。
信号 1：连续子数组 / 连续子串
只要看到“连续”这两个字，就要敏感一点。
比如：
-
最长连续不重复子串
-
最小覆盖子串
-
长度最小的子数组
-
和大于等于 target 的最短子数组
这些经常就是滑动窗口。
信号 2：求最长 / 最短
尤其是：
-
最长满足条件
-
最短满足条件
这两类非常爱用滑动窗口。
信号 3：窗口里的东西会动态变化
比如：
-
字符出现次数
-
元素和
-
是否有重复字符
这也很像滑动窗口。
11. 第三道经典题：无重复字符的最长子串
题目大意：
给定一个字符串 s，找出不含重复字符的最长子串长度。
比如：
"abcabcbb"
答案是：
3
因为最长无重复子串是 "abc"。
11.1 为什么这题想到滑动窗口
因为题目要求的是：
-
子串
-
而且是连续的
-
还要求最长
这三个特征一出来，滑动窗口味道就很重了。
11.2 思路
我们维护一个窗口 [left, right]，保证窗口里没有重复字符。
每次让 right 往右扩：
-
如果新字符没重复，继续扩
-
如果重复了，就移动
left，直到窗口重新合法
然后每次更新窗口长度最大值。
11.3 代码写法 1：用哈希表计数
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> cnt;
int left = 0;
int ans = 0;
for (int right = 0; right < s.size(); right++) {
cnt[s[right]]++;
while (cnt[s[right]] > 1) {
cnt[s[left]]--;
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
11.4 这段代码怎么理解
先把 s[right] 放进窗口：
cnt[s[right]]++;
如果出现重复：
while (cnt[s[right]] > 1)
说明当前窗口不合法了，那就不断缩左边：
cnt[s[left]]--;
left++;
直到窗口重新变成“无重复”。
然后更新答案：
ans = max(ans, right - left + 1);
11.5 这题你要学到什么
这道题最核心的不是代码，而是窗口思维：
滑动窗口常见过程
-
右边扩张，把新元素加入窗口
-
判断窗口是否合法
-
不合法就缩左边
-
合法后更新答案
这个流程特别通用。
后面很多窗口题本质上都差不多。
12. 滑动窗口和普通双指针的区别
很多人学到这里会有点混。
其实可以这样区分：
普通双指针
更强调两个位置怎么配合移动。
比如：
-
左右夹逼
-
快慢指针
滑动窗口
更强调维护一个连续区间。
比如：
-
[left, right]这段里字符不能重复 -
[left, right]这段里的和要满足条件 -
[left, right]这段长度要尽量大或尽量小
所以你可以理解成：
滑动窗口其实是双指针的一种常见用法。
13. 前缀和到底是什么
前缀和就是：
先把前面累加起来。
比如数组：
nums = [1, 2, 3, 4]
我们定义：
pre[i]
表示前 i 个数的和。
注意这里一般写成：
pre[0] = 0
pre[1] = 1
pre[2] = 1 + 2 = 3
pre[3] = 1 + 2 + 3 = 6
pre[4] = 1 + 2 + 3 + 4 = 10
所以前缀和数组通常比原数组多开一个位置。
写法：
vector<int> pre(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++) {
pre[i + 1] = pre[i] + nums[i];
}
14. 前缀和有什么用
它最重要的用途就是：
快速求任意一段区间和。
比如要算：
nums[l] + nums[l+1] + ... + nums[r]
不用每次都重新加一遍，直接：
pre[r + 1] - pre[l]
就出来了。
14.1 为什么是这个公式
比如：
nums = [1, 2, 3, 4]
pre = [0, 1, 3, 6, 10]
要算下标 1 到 3 的和，也就是：
2 + 3 + 4 = 9
那就是：
pre[4] - pre[1] = 10 - 1 = 9
本质就是：
大的前缀和 - 前面不要的部分
15. 前缀和最常出现在哪些题里
场景 1：多次求区间和
比如一堆查询：
-
求第 l 到 r 的和
-
求某段区间是否满足条件
场景 2：子数组和问题
比如：
-
和为 k 的子数组
-
连续数组和
-
子矩阵和
场景 3：前缀和 + 哈希
这个组合是 Hot100 高频组合。
比如：
-
和为 k 的子数组
这类题后面你会反复见到。
16. 一个最基础的前缀和模板
vector<int> pre(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++) {
pre[i + 1] = pre[i] + nums[i];
}
求区间 [l, r] 的和：
int sum = pre[r + 1] - pre[l];
这个模板你直接背就行。
17. 前缀和和滑动窗口有什么区别
这两个也很容易混。
滑动窗口
更适合：
-
连续区间
-
动态扩张和收缩
-
求最长、最短
-
条件会随着窗口变化
比如：
-
最长无重复子串
-
最短子数组长度
前缀和
更适合：
-
快速算区间和
-
一次预处理，多次查询
-
和的统计问题
比如：
-
多次查询区间和
-
和为 k 的子数组
18. 你现在先不用死磕最难的题
这三个知识点里，前期最容易上手的是：
-
双指针
-
滑动窗口
前缀和刚开始会稍微绕一点，尤其是和哈希表结合的时候。
所以你现在的目标不是把所有题一次学透，而是先建立感觉：
看到这些题眼要有反应
-
原地修改数组 -> 快慢指针
-
两边夹逼 -> 左右指针
-
连续子串 / 最长最短 -> 滑动窗口
-
区间和 -> 前缀和
这一步非常关键。
19. 三个最常用模板，先背下来
19.1 快慢指针模板
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (满足条件) {
nums[slow] = nums[fast];
slow++;
}
}
常见用途：
-
去零
-
去重
-
删除元素
19.2 左右指针模板
int left = 0;
int right = nums.size() - 1;
while (left < right) {
if (满足条件) {
left++;
} else {
right--;
}
}
常见用途：
-
有序数组找和
-
回文
-
容器盛水
-
三数之和
19.3 滑动窗口模板
int left = 0;
for (int right = 0; right < nums.size(); right++) {
// 把 nums[right] 加入窗口
while (窗口不合法) {
// 缩小左边
left++;
}
// 更新答案
}
常见用途：
-
最长子串
-
最短子数组
-
覆盖类问题
-
计数类窗口问题
20. 这一篇你最容易犯的错误
错误 1：双指针乱移动
不是两个指针都随便动。
每次怎么动，一定要有理由。
比如盛水题里，是因为短板限制面积，所以移动短板。
错误 2：窗口不合法时不缩
滑动窗口最关键的一步就是：
不合法就缩。
有些人只会扩，不会缩，那窗口题就很容易写崩。
错误 3：前缀和下标写乱
前缀和最容易错的是：
pre[i + 1] = pre[i] + nums[i];
还有：
区间和 = pre[r + 1] - pre[l];
这个你要多看几遍。
21. 这一篇学完，你应该达到什么程度
你不需要现在就把所有题都秒掉，但至少要做到：
会判断
-
什么题像双指针
-
什么题像滑动窗口
-
什么题像前缀和
会写基础模板
-
快慢指针
-
左右指针
-
滑动窗口
-
前缀和数组
会做最基础的经典题
-
移动零
-
盛最多水的容器
-
无重复字符的最长子串
做到这一步，你就已经真正开始刷 Hot100 了。
22. 给自己记的几个口诀
可以直接记：
原地修改数组，先想快慢指针
左右两边逼近，先想左右指针
连续子串求最长最短，先想滑动窗口
求区间和，先想前缀和
再记一句：
滑动窗口本质上也是双指针
23. 本篇总结
这一篇开始接触真正的题型思维了。
现在最重要的，不是去背很多花哨技巧，而是先把这三个模型刻进脑子里：
-
双指针：两个位置配合着走
-
滑动窗口：维护一个连续区间
-
前缀和：提前累计，快速算区间和
其中当前最该先练熟的是：
-
快慢指针
-
左右指针
-
滑动窗口基础题
前缀和先打基础，后面再和哈希表结合，威力会更大。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
4
0- 0
已为社区贡献3条内容
所有评论(0)