企业官网建设流程全解析

LeetCode Hot 100 里的双指针专题，我前后刷了两遍，每一遍都有新的理解。第一次是把题解背下来，第二次才彻底想明白：为什么两个指针来回移动几下，就能把一个 O(n^2) 的暴力解法变成 O(n)？如果你正在准备算法面试，或者已经把链表、二分这些基础题过了一遍，想系统整理哪几类题能归到“双指针”，这篇应该能帮上忙。我会用 C++ 写题解，代码里也顺带标注一些在 C++ 里特别容易踩的坑。

这一专题几乎每次面试都会被问到，核心题型不算多，但覆盖了数组、字符串、链表三类场景。整理清楚之后，你会发现在 Hot 100 里除了“滑动窗口”，还有大概十道题本质上都在反复用同一套指针移动逻辑，只是穿上了不同的外衣。下面我就按“思路 -> 模板 -> 经典题 -> 进阶 -> 排错”的顺序讲。

1. 双指针到底在解决什么问题

1.1 从两数之和 II 看双指针为什么比暴力快

直接拿“两数之和 II - 输入有序数组”说事。题目要求在一个下标从 1 开始的有序数组里找两个数，使它们的和等于 target。最土的做法是两层循环枚举所有数对，遇到和等于 target 就返回，复杂度 O(n^2)。但数组是有序的，这一条信息没有被利用。

双指针的做法很直白：left 指向数组开头，right 指向数组结尾。计算 sum = numbers[left] + numbers[right]：

• sum == target，直接返回；
• sum < target，说明左边的数太小了，只能把 left 往右移；
• sum > target，说明右边的数太大了，只能把 right 往左移。

为什么这种移动方式不会漏掉正确答案？假设正确答案是 numbers[i] 和 numbers[j]，且 i < j。当 left 还没走到 i 时，不管 right 在哪，如果当前的 right 在 j 的右边，sum 一定大于 target，于是 right 会一直向左收；如果 left 已经越过了 i，那从 i 这个位置出发的答案早已被考虑过了。换句话说，每一次移动都排除了一个“不可能再有解”的区间。这个思想贯穿所有左右指针题。

从复杂度上看，left 和 right 总共只会移动 n 次，所以是 O(n)。这就是双指针最迷人的地方：用有序性换掉一层枚举循环。

1.2 三个判断条件：哪些题目能用双指针

后来刷多了，我总结出三个判断条件，基本能筛掉九成题。

第一，问题能否建模成两个元素之间的关系。找两数之和、三数之和、盛水容器里的面积，都是两个位置共同决定结果。如果题目的答案要同时依赖数组里两个位置，双指针就有戏。

第二，指针的移动方向是否单调。这里“单调”不是指数组本身单调，而是指当某个指针移动到某个位置后，如果当前组合不满足条件，那向某个方向移动不会再带来更优解。比如三数之和里，固定第一个数后，sum 小于 0 就必须增大 left，因为 left 再往左是不可能的，while(left < right) 这个结构保证了收敛。

第三，无序的输入能不能先排序。第一道两数之和不允许排序（因为要返回原数组下标），所以不能用双指针；但第二道题输入已经有序，排序也没有破坏返回下标的约束，于是就能用。三数之和、盛水容器都能排序，因为它们输出的是数值本身而不是下标。这个条件经常被忽略，我见过不少人把需要返回原下标的题直接排序，然后整个结果全错。

满足这三个条件的题，很大概率可以用双指针把复杂度往下压一档。不满足的，通常也就别硬套了。

2. C++ 的两种双指针模板与实现细节

2.1 左右指针模板：从两端向中间逼近的写法与坑

左右指针的代码其实出奇地短：

int left = 0, right = (int)nums.size() - 1; while (left < right) { if (check(left, right)) { // 记录答案，具体看题目 } if (nums[left] + nums[right] < target) { ++left; } else { --right; } }

这里有一个很多人一开始会写错的点：循环条件是 left < right，不是 left <= right。因为双指针题里两个指针代表的是两个不同的位置，相遇之后区间宽度为 0，已经不存在有效的数对了。如果你写成 <=，在个别题目里会把自己搞进死循环，尤其是那种“记录完答案还要继续移动指针”的题。

另一个细节是“记录答案”和“移动指针”的顺序。像两数之和这种题，找到答案直接 return，顺序无所谓；但像三数之和这种题，找到答案后要先把所有相同的数跳过，再同时收缩两个指针，否则会重复输出同一个三元组。我的习惯是：先判断当前组合是否已经是答案，再决定下一步怎么走，不要反过来。

2.2 快慢指针模板：一个探路一个收尾的原地操作

快慢指针专门处理一类“原地操作”的题目。比如把一个数组里的零全部移到末尾，同时保持非零元素的相对顺序。很多人的第一反应是开一个新数组，但题目要求原地。

模板长这样：

int slow = 0; for (int fast = 0; fast < (int)nums.size(); ++fast) { if (nums[fast] != 0) { swap(nums[slow], nums[fast]); ++slow; } }

理解快慢指针的关键是：fast 负责探索整个数组，每遇到一个符合条件的元素，就把它放到 slow 指向的位置，然后 slow 前进。slow 左边的区间永远是已经处理好的部分。这个“维护有效前缀”的视角，比把代码背下来重要得多。很多变体题，比如删除排序数组中的重复项，把判断条件换成 nums[fast] != nums[slow - 1] 即可，核心思想完全一样。

快慢指针和左右指针最大的区别在哪？左右指针面对的是“从两边向中间收敛”的问题，快慢指针面对的是“一个扫全图、一个收结果”的问题。前者通常利用有序性，后者通常利用元素种类的可分性。拿到题先想清楚是哪一类，再套模板，思路会顺很多。

2.3 C++ 双指针的三个易错点：类型、边界、引用

C++ 写双指针，有几个坑几乎每场笔试都能见到。

第一个是无符号整数。nums.size() 返回的是 size_t，如果你直接写 int right = nums.size() - 1，当 nums 为空时 right 会变成 4294967295 这样的巨大正数，while 循环直接崩。要么先判空，要么先把 size 强转成 int。我现在一律写 int n = (int)nums.size()，省心。

第二个是整数溢出。虽然 LeetCode 的测试用例大部分不会让 int 溢出，但“两数之和”这类题里两个 int 相加最大值可能逼近 2^31，稳妥起见我会在相加前先把值转成 long long。三数之和里三个数相加亦然。这个习惯不亏。

第三个是排序丢下标。前面已经提过，凡是题目要求返回原数组下标的情况，排序前必须先把下标和值一起打包进 struct，或者存到 map 里。这里不再展开。

3. 三道最经典 Hot 100 题拆解

3.1 三数之和去重关键：排序+固定一数+双指针

三数之和是双指针专题里最重要的一道题，没有之一。题目要求找出数组中所有和为 0 的三元组，且不能重复。

整体的思路有三个步骤：先排序，再固定第一个数，最后用双指针在剩余区间里找两数之和。固定第一个数为什么要排序？因为排序后才可能用左右指针。如果不排序，双指针无法保证单调性。

完整代码：

vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int n = (int)nums.size(); for (int i = 0; i < n; ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { res.push_back({nums[i], nums[left], nums[right]}); while (left < right && nums[left] == nums[left + 1]) ++left; while (left < right && nums[right] == nums[right - 1]) --right; ++left; --right; } else if (sum < 0) { ++left; } else { --right; } } } return res; }

这里最容易被绕晕的就是去重逻辑。外层循环里的 if (i > 0 && nums[i] == nums[i - 1]) 是防止同一个第一个数被重复使用；内层找到一组答案后，要先把 left 和 right 指向的下一个数字都跳过重复，再同时收缩，否则同一组三元组会被多次记录。

注意：有一个非常常见的错误是把外层去重写成 nums[i] == nums[i + 1]。这两个看起来差不多，实际效果完全不同。写成 i+1 会跳过“当前这个数作为第一个数”的所有情况，直接导致漏解。比如 [-1, -1, 2] 这个三元组，如果第一个 -1 因为和第二个 -1 相同被跳过，就永远找不到答案了。正确写法是跟前一个比较，而不是跟后一个比较。

3.2 盛最多水的容器：为什么每次都要移动矮的那边

这道题输入是一个数组，每个元素代表墙的高度，要找两根柱子之间能盛的最大水量。公式是：

area = (right - left) * min(height[left], height[right])

暴力枚举所有柱子对，能过但很慢。双指针的优化从两端开始，每次都移动高度较小的一边。为什么？因为面积由两个因素决定：宽度和两侧较低的墙。如果把较高的那一边向内移动，宽度在缩减，而 min 的高度只会变得更小或不变，面积不可能增大；如果把较矮的那一边向内移动，min 的高度有可能变大，面积才有机会变大。

这个逻辑其实就是贪心的思想：每一步都主动放弃“不可能成为最优解”的区间。代码非常短：

int maxArea(vector<int>& height) { int left = 0, right = (int)height.size() - 1; int res = 0; while (left < right) { int area = min(height[left], height[right]) * (right - left); res = max(res, area); if (height[left] < height[right]) { ++left; } else { --right; } } return res; }

有同学会问：如果 height[left] == height[right] 时移动哪边？代码里走了 else 分支，也就是移动 right。其实两边都一样，因为无论如何下一步都会重新计算，这个相等的情况不会影响最终答案。实测下来，移动哪边都不会漏解。

这道题我还建议用一种“反证法”的方式来验证：假设最优解在某个区间 (i, j)，如果当前 left 还不到 i，而 right 已经超过了 j，那必然有一次移动会让指针离开最优区间，那次移动一定是移走了较矮的一侧，因为较高的一侧移走了会和“最优解”矛盾。想通这一点，贪心的正确性就基本握住了。

3.3 移动零：快慢指针原地交换的最小实现

移动零题目本身很简单：把数组里所有 0 移到末尾，非零元素保持相对顺序。但它是快慢指针思想的最佳入门题。

双指针写法：

void moveZeroes(vector<int>& nums) { int slow = 0; for (int fast = 0; fast < (int)nums.size(); ++fast) { if (nums[fast] != 0) { swap(nums[slow], nums[fast]); ++slow; } } }

模拟一遍就明白了：fast 每遇到一个非零元素，就把它和 slow 位置的元素交换。如果 slow 位置本身就是非零的，那交换的两个位置相同，结果不变；如果 slow 指向的是已经排好的首部区域，fast 则指向后面一个非零元素，交换后这个非零元素被搬到了前面，slow 再前移。

这个过程里 slow 始终指向“下一个非零元素应该放的位置”，而 fast 负责扫整个数组。等 fast 走到头，所有非零元素都在 slow 左边，剩下的位置自然全是 0。这么做的时间复杂度是 O(n)，空间 O(1)，满足很多面试官的额外追问。

要注意的一个小坑：如果数组长度为 1，或者数组全是 0，fast 每次都不满足条件，slow 一直停在 0，不会越界，所以没问题。掉以轻心反而会在“给空数组”的测试用例上翻车。

4. 从双指针到进阶用法

4.1 接雨水：双指针如何把动态规划压缩到 O(1) 空间

接雨水在 Hot 100 里的位置很特别：它既可以用动态规划，也可以用双指针。如果你先做动态规划版本，再理解双指针，会对“指针移动为什么有效”有更深的感觉。

动态规划的思路是：对于每个位置 i，它能接到多少水，取决于它左边最高的柱子和右边最高的柱子中较矮的那个。如果这个“较矮的高墙”高于 height[i]，就能接到高度差的水。所以要开两个数组 leftMax 和 rightMax 分别预处理。

双指针的做法把空间压缩到 O(1)，核心逻辑变成了：当 height[left] < height[right] 时，处理 left 位置；否则处理 right 位置。为什么能这么做？关键在“结算较矮的一侧”。以处理 left 为例，leftMax 已经记录了 left 左侧扫过的最高的墙，而右侧当前边界 height[right] 比 left 位置的柱子高。由于 left 能移动到当前位置，说明右侧的墙比 left 左侧遇到过的所有柱子都高，因此右侧最终的峰值一定不会低过 leftMax。所以 left 位置能接多少水，就完全由 leftMax 决定。

代码：

int trap(vector<int>& height) { int left = 0, right = (int)height.size() - 1; int leftMax = 0, rightMax = 0; int ans = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { ans += leftMax - height[left]; } ++left; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { ans += rightMax - height[right]; } --right; } } return ans; }

考试时如果一时没想起来双指针版本，动态规划版本也能过关。双指针版本的魅力在于把两个预处理数组变成了两个滚动变量，思路更逼近“左右高墙的临界点”。

4.2 颜色分类：三指针解决荷兰国旗问题

颜色分类题要求原地把数组排成 0、1、2 的顺序，只有三个值。它被归到双指针专题，严格来说是双指针的升级版：三指针。

思路是维护三个区域：p0 指向下一个 0 应该放的位置，p2 指向下一个 2 应该放的位置，cur 从头扫到尾。cur 遇到 0，就和 p0 交换，p0 和 cur 都前进；遇到 2，就和 p2 交换，p2 后退，但 cur 不前进；遇到 1，cur 直接前进。

为什么遇到 2 时 cur 不能前进？因为从 p2 换过来的数可能是 1，也可能是 0，还没有被归类过，必须原地再检查一次。这个细节是荷兰国旗问题的灵魂，也是最容易写错的地方。

完整代码：

void sortColors(vector<int>& nums) { int p0 = 0, p2 = (int)nums.size() - 1; int cur = 0; while (cur <= p2) { if (nums[cur] == 0) { swap(nums[p0], nums[cur]); ++p0; ++cur; } else if (nums[cur] == 2) { swap(nums[p2], nums[cur]); --p2; } else { ++cur; } } }

你可以把这道题理解成“两个左右指针 + 一个扫描指针”的配合。它告诉我们：双指针的框架并不死板，根据需要可以扩展成三个指针，核心依然是指针所划定的边界。

4.3 最长回文子串：中心向外扩展的双指针变体

最长回文子串是字符串题里的一道经典，虽然分类往往不在双指针专题里，但它内部用的就是双指针的思想，只不过方向相反：不是从两端向中间夹，而是从中心向两边扩。

实现思路：枚举每个位置作为中心点，奇数长度回文中心是一个字符，偶数长度回文中心是两个相邻字符。对每一种中心，用两个指针向左、向右同时扩展，直到字符不同或越界。

string longestPalindrome(string s) { int n = (int)s.size(); if (n < 2) return s; int start = 0, maxLen = 1; for (int i = 0; i < n; ++i) { auto expand = [&](int l, int r) -> int { while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; } return r - l - 1; }; int len1 = expand(i, i); int len2 = expand(i, i + 1); int len = max(len1, len2); if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; } } return s.substr(start, maxLen); }

这里 expand 函数里的 while 循环，本质就是两个指针分别往两侧探路。掌握了“指针移动的方向不是固定的，既可以相向也可以相背”这一点，字符串类的很多题也会豁然开朗。

5. 踩坑实录：常见错误与排查方法

5.1 死循环和漏解的两种典型场景

我刷题时遇到最多的死循环，基本都出在“记录答案后忘记移动指针”和“移动指针的幅度小于应有的幅度”两种场景。

第一种典型是三数之和里找到一组答案后，只把 left 或 right 其中一个移动一个单位，另一个没动。比如 sum == 0 后只写了 ++left，没有写 --right，那 left 到下一个位置后，right 还是原来的位置，如果 nums[left+1] 和 nums[left] 相等，就还会再匹配出同一组三元组，甚至陷入无限循环。解决方式前面已经写了：两个指针都跳过重复并收缩。

第二种典型是快慢指针里 slow 只在满足条件时移动，但 fast 的移动循环被误写成 while 而不是 for。比如移动零里如果用 while 代替 for，忘记在每次循环末尾给 fast 加一，一定会卡死。我的建议是：写完代码先自己走一遍两到三行的样例，慢慢挪动指针，确认每一步都必然前进。

漏解的场景集中在去重逻辑写反。三数之和外层去重写成 nums[i] == nums[i+1] 会漏解，前面已经说过了。还有个容易漏的是内层去重后，忘记再 ++left / --right 一下，导致一轮循环结束后指针没有越过重复区间，下一轮匹配的还是同一批重复值。

5.2 边界条件和整数溢出的排查细节

边界条件，核心就是三个词：空、单个、相等。

• 空数组或空字符串，很多双指针版本会直接访问 nums[0]，必须先判空；
• 单个元素，比如移动零里数组只有一个 0，slow 始终为 0，没问题，但如果你在 while 循环里写了 right - 1 之类的操作就要小心；
• 相等元素，比如盛水容器里 height[left] == height[right] 时无论移动哪一边都不会错，但有些变体题遇到相等时移动策略不同会得出不同结果，需要先仔细读题。

整数溢出这块，C++ 的 int 范围是大约正负 2.1e9，如果题目的数值范围比较大，比如两数之和的数组成员可以到 10^9，两个相加就到 2e9，还在 int 范围内，但三数之和呢，三个 10^9 就是 3e9，已经爆了。LeetCode 题目通常不会把这些极端情况全放在小数据里测，但面试官扩展时喜欢追问。稳妥做法是统一用 long long 参与计算，或者在相加前先做一次类型转换。

5.3 常见错误速查表：几道高频题的坑

我把平时遇到的、以及在群聊里看大家问得最多的问题整理成了一张表：

这张表还可以继续补充，但核心规律就是：双指针的题，大部分错误都能归结为“指针移动的时机不对”或“边界维护的范围不清”。debug 的时候顺着这两条线去查，一般都能很快定位。

我个人刷下来还有一个习惯：每道双指针题做完了，都会在草稿纸上画一下指针移动的完整路线，然后问自己一个问题——刚才那步移动为什么不会漏掉最优解？如果答不上来，说明这道题还没真正搞懂。这个习惯帮我避开了大量“背题解”式的无效刷题。建议你也试试。

最后再分享一个小技巧：把双指针和滑动窗口放在一起对比学习。左右指针是两端夹逼，快慢指针是单向推进，滑动窗口是同向双指针的进阶，三者本质上都是“用两个边界来维护一个区间”。透彻理解其中一种，另外两种的代码理解起来会快很多。