【LeetCode Cookbook（C++ 描述）】双指针技巧实战：数组问题高效解法

1. 双指针技巧入门：为什么它能高效解决数组问题

第一次接触双指针技巧是在刷LeetCode第27题"移除元素"时。当时我用暴力解法两层循环硬怼，虽然通过了测试，但看到时间复杂度O(n²)的惨淡结果，就知道肯定有更优解。直到发现快慢指针的解法，才真正体会到算法优化的美妙。

双指针的核心思想很简单：用两个指针协同工作，减少不必要的遍历。想象你在整理书架，一本本检查并移除不需要的书。暴力解法相当于每找到一本要移除的书，就把后面所有书往前挪一格；而快慢指针则像两个人配合，一个负责检查书籍是否需要保留，另一个负责把保留的书放到新位置。

这种技巧特别适合处理数组的原地修改问题。比如：

• 移除特定元素（LeetCode 27）
• 去重（LeetCode 26）
• 移动零（LeetCode 283）

// 快慢指针移除元素的典型实现 int removeElement(vector<int>& nums, int val) { int slow = 0; for (int fast = 0; fast < nums.size(); fast++) { if (nums[fast] != val) { nums[slow++] = nums[fast]; } } return slow; }

这个解法之所以高效，是因为它把时间复杂度从O(n²)降到了O(n)。快指针fast勇往直前探路，慢指针slow稳扎稳打构建新数组，每个元素只被处理一次。我在实际编码中发现，理解快慢指针的关键是明确：

1. fast的职责：遍历所有元素
2. slow的定位：指向下一个有效元素应该存放的位置

2. 快慢指针的进阶应用：从数组到链表

掌握了基础用法后，我发现快慢指针的适用场景比想象中更广。它不仅适用于数组，还能巧妙解决链表问题。比如经典的链表去重问题（LeetCode 83），用快慢指针可以写出极其优雅的解法。

记得有次面试被要求写一个检测链表环的算法。当时我灵机一动，用快慢指针模拟"龟兔赛跑"：

• 慢指针每次走一步
• 快指针每次走两步 如果有环，快指针最终会追上慢指针。这个思路后来才知道是Floyd判圈算法。

bool hasCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; }

快慢指针在链表问题中展现出独特优势：

1. 空间效率：O(1)的额外空间
2. 时间效率：通常只需遍历1-2次链表
3. 思维简洁：模拟现实中的追逐过程

3. 左右指针：数组中的双向奔赴

如果说快慢指针是同向移动的"好兄弟"，那么左右指针就是相向而行的"有缘人"。我第一次体会到左右指针的威力是在解"两数之和II"（LeetCode 167）时。

传统暴力解法需要O(n²)时间，而左右指针只需要O(n)：

vector<int> twoSum(vector<int>& numbers, int target) { int left = 0, right = numbers.size() - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) return {left+1, right+1}; else if (sum < target) left++; else right--; } return {-1, -1}; }

左右指针特别适合处理有序数组的问题，比如：

• 二分查找（本身就是左右指针的经典应用）
• 反转数组（LeetCode 344）
• 有序数组的平方（LeetCode 977）

在实际编码中，我发现左右指针有几种常见模式：

1. 相向而行：一个从头开始，一个从尾开始，向中间靠拢
2. 背向而行：从中间开始，向两端移动
3. 异步移动：根据条件决定移动哪个指针

4. 滑动窗口：双指针的高级形态

滑动窗口是我认为双指针技巧中最精妙的应用。第一次接触是在解"长度最小的子数组"（LeetCode 209）时，暴力解法直接超时，而滑动窗口解法优雅高效。

滑动窗口的精髓在于：

1. 用left和right指针维护一个窗口
2. 先扩展right直到满足条件
3. 然后收缩left寻找最优解
4. 像蚯蚓一样在数组上蠕动前进

int minSubArrayLen(int target, vector<int>& nums) { int left = 0, right = 0, sum = 0; int min_len = INT_MAX; for (; right < nums.size(); right++) { sum += nums[right]; while (sum >= target) { min_len = min(min_len, right - left + 1); sum -= nums[left++]; } } return min_len == INT_MAX ? 0 : min_len; }

滑动窗口适用于解决子数组/子串问题，特别是需要满足某些条件的最短/最长子数组。比如：

• 最小覆盖子串（LeetCode 76）
• 无重复字符的最长子串（LeetCode 3）
• 字符串排列（LeetCode 567）

在实际应用中，我发现滑动窗口有几个易错点：

1. 窗口收缩条件判断
2. 结果更新的时机
3. 边界条件处理（特别是字符串结束时的处理）

5. 双指针的边界条件与调试技巧

即使理解了双指针的原理，实际编码时还是会遇到各种边界问题。记得有次做"移除元素"题目，因为没处理好slow指针的移动，导致最后一个元素总是处理错误。

经过多次踩坑，我总结出几个调试技巧：

1. 打印指针位置：在循环中加入调试输出，观察指针移动

cout << "fast:" << fast << " slow:" << slow << endl;

2. 极端测试用例：空数组、单元素数组、全相同元素数组
3. 可视化跟踪：在纸上画出指针移动过程

常见边界陷阱包括：

• 指针越界（特别是right指针）
• 空输入处理
• 元素全部相同或全部需要移除的情况
• 更新结果的时机不对

6. 双指针与其他算法的组合应用

随着刷题经验增加，我发现双指针经常与其他算法搭配使用，产生1+1>2的效果。比如在"三数之和"（LeetCode 15）中，双指针与排序的结合堪称经典。

解题思路：

1. 先排序固定一个数
2. 然后用左右指针在剩余数组中寻找两数之和

vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res; for (int i = 0; i < nums.size(); i++) { if (i > 0 && nums[i] == nums[i-1]) continue; int left = i+1, right = nums.size()-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; }

其他常见组合模式：

• 双指针+哈希表（解决某些查找问题）
• 双指针+贪心算法（如容器盛水问题）
• 双指针+二分查找（优化搜索范围）

7. 从LeetCode到实际工程：双指针的实用价值

很多人觉得算法题只是面试需要，其实双指针思想在实际工程中大有可为。我曾经优化过一个日志处理系统，用滑动窗口算法将处理时间从小时级降到分钟级。

典型应用场景包括：

1. 大数据处理：流式数据的时间窗口分析
2. 文件比对：逐行比较两个大文件
3. 内存优化：原地处理数据，减少拷贝
4. 实时系统：滑动窗口限流算法

比如实现一个简单的文件差异检测：

void compareFiles(ifstream& file1, ifstream& file2) { string line1, line2; int ptr1 = 0, ptr2 = 0; while (getline(file1, line1) && getline(file2, line2)) { if (line1 != line2) { cout << "差异行: file1#" << ptr1 << " vs file2#" << ptr2 << endl; } ptr1++; ptr2++; } // 处理剩余行... }

在工程实践中，双指针的价值体现在：

1. 空间效率：减少临时存储
2. 时间效率：降低时间复杂度
3. 代码简洁：逻辑清晰易维护

8. 双指针解题的思维训练法

要真正掌握双指针，光刷题还不够，需要系统化的思维训练。我总结了一套"三步法"：

1. 问题分析：判断是否适合双指针
   • 是否涉及顺序遍历？
   • 能否通过指针移动减少计算？
2. 指针定义：明确每个指针的语义
   • 快慢指针：谁负责遍历？谁负责写入？
   • 左右指针：移动条件是什么？
3. 移动规则：确定指针如何变化
   • 什么条件下移动？
   • 移动步长是多少？

以"颜色分类"问题（LeetCode 75）为例：

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

训练时可以尝试：

1. 先写暴力解法，再优化
2. 画图辅助理解指针移动
3. 对每个问题至少思考两种不同的双指针解法

9. 常见误区与性能优化

即使是经验丰富的开发者，使用双指针时也容易陷入一些误区。我曾经在一个项目中错误地使用了快慢指针，导致处理特殊case时出现bug。

常见误区包括：

1. 指针移动条件错误：该移动时没移动，不该移动时移动了
2. 边界处理不当：特别是数组开始和结束时的处理
3. 过度优化：为了用双指针而用，反而使代码复杂

性能优化建议：

1. 减少不必要的操作：比如在滑动窗口中避免重复计算
2. 利用有序性：排序后往往能简化双指针逻辑
3. 提前终止：找到解后立即返回

以"盛最多水的容器"（LeetCode 11）为例，优化后的解法：

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

关键优化点：

1. 每次移动较矮的那边（因为高度取决于短板）
2. 即时计算并更新最大面积
3. 单次遍历O(n)时间复杂度

10. 从经典题目到举一反三

最后，我建议通过经典题目掌握双指针的核心模式，然后举一反三。以下是必刷题目清单：

快慢指针系列：

• 删除排序数组中的重复项（LeetCode 26）
• 移动零（LeetCode 283）
• 寻找重复数（LeetCode 287）

左右指针系列：

• 反转字符串（LeetCode 344）
• 验证回文串（LeetCode 125）
• 三数之和（LeetCode 15）

滑动窗口系列：

• 无重复字符的最长子串（LeetCode 3）
• 字符串的排列（LeetCode 567）
• 最大连续1的个数III（LeetCode 1004）

每做完一道题，可以问自己：

1. 指针的初始位置合理吗？
2. 移动条件是否覆盖所有情况？
3. 能否进一步优化时间或空间？

比如做完"无重复字符的最长子串"后，可以尝试变种题：

• 最多包含两个不同字符的最长子串
• 至少包含K个重复字符的最长子串
• 替换后的最长重复字符

这种刻意练习能帮助建立对双指针的直觉，遇到新问题时能快速识别适用场景。