双指针、滑动窗口与前缀和：算法解题三大核心模式详解

1. 算法解题思维入门双指针、滑动窗口与前缀和作为一名刷过上千道算法题的过来人我深知初学者在面对LeetCode时的困惑。很多人卡在知道语法但不知道如何解题的阶段这篇文章就是要帮你突破这个瓶颈。我们将重点探讨三种高频解题模式双指针、滑动窗口和前缀和这些技巧在Hot100题库中出现率超过60%。刚开始刷题时最痛苦的不是写不出代码而是连解题方向都找不到。我记得第一次做盛水容器那道题时盯着屏幕半小时毫无头绪。直到理解了双指针的精髓才恍然大悟。本文将分享我从实战中总结的识别特征和模板代码帮你建立解题直觉。2. 核心解题模式解析2.1 双指针协同工作的两个下标双指针不是真的指针而是用两个下标协同遍历数据结构的技巧。它之所以高效是因为通过两个位置的配合可以将O(n²)的暴力解法优化到O(n)。根据移动方式不同主要分为两种类型2.1.1 左右指针对撞指针典型特征一个指针在起始位置(left)一个在末尾(right)两者向中间移动直到相遇适用于有序数组或需要从两端同时处理的情况int left 0; int right nums.size() - 1; while (left right) { if (condition) { left; // 左指针右移 } else { right--; // 右指针左移 } }适用场景有序数组的两数之和LeetCode 167盛最多水的容器LeetCode 11三数之和的内部循环LeetCode 15回文字符串验证LeetCode 1252.1.2 快慢指针同向指针典型特征两个指针从同侧出发快指针(fast)负责探索慢指针(slow)负责记录常用于原地修改数组或链表问题int slow 0; for (int fast 0; fast nums.size(); fast) { if (满足特定条件) { nums[slow] nums[fast]; slow; } }适用场景删除有序数组中的重复项LeetCode 26移动零LeetCode 283移除指定元素LeetCode 27链表中间节点LeetCode 8762.2 滑动窗口动态维护的区间滑动窗口本质上是双指针的进阶用法特别适合处理连续子数组/子串问题。它的核心思想是维护一个满足条件的动态区间通过调整窗口边界来寻找最优解。标准模板int left 0; for (int right 0; right s.size(); right) { // 扩展右边界 window.add(s[right]); while (窗口不满足条件) { // 收缩左边界 window.remove(s[left]); left; } // 更新结果 res max(res, right - left 1); }关键点在于right每步必右移尝试扩展窗口当窗口不满足条件时left右移收缩窗口在每次合法窗口时更新最优解适用场景特征题目要求连续子数组/子串需要找最长/最短满足条件的区间涉及字符出现次数、元素和等动态统计典型题目无重复字符的最长子串LeetCode 3最小覆盖子串LeetCode 76长度最小的子数组LeetCode 209字符串排列LeetCode 5672.3 前缀和区间查询的利器前缀和是一种预处理技术通过预先计算累计和可以将区间求和的复杂度从O(n)降到O(1)。这在需要频繁查询子数组和的场景下特别有用。实现步骤构建前缀和数组比原数组多一位利用前缀和差值计算任意区间和vectorint preSum(nums.size() 1, 0); for (int i 0; i nums.size(); i) { preSum[i 1] preSum[i] nums[i]; } // 计算nums[l..r]的和 int sum preSum[r 1] - preSum[l];适用场景频繁查询数组的区间和统计满足特定和的子数组数量二维矩阵的子矩阵和计算与哈希表结合解决复杂问题如和为K的子数组典型题目区域和检索 - 数组不可变LeetCode 303和为K的子数组LeetCode 560连续的子数组和LeetCode 523二维区域和检索LeetCode 3043. 模式识别与解题策略3.1 如何识别题目类型3.1.1 双指针的识别信号题目要求原地修改数组/链表示例移动零、删除重复项解法快慢指针保持已处理区域涉及有序数组的查找示例两数之和、三数之和解法左右指针夹逼需要从两端向中间处理示例盛水容器、回文判断解法对撞指针比较移动3.1.2 滑动窗口的识别信号关键词连续子数组/子串示例最长无重复子串解法维护字符出现频率表极值要求最长/最短满足条件示例最短子数组长度解法动态调整窗口边界窗口性质动态变化示例覆盖所有字符的最小子串解法统计字符覆盖情况3.1.3 前缀和的识别信号频繁查询区间和示例多次求子数组和解法预处理前缀和数组统计特定和的子数组示例和为K的子数组个数解法前缀和哈希表计数数据不可变但查询多示例固定数组的多次求和解法一次预处理多次查询3.2 解题模板与变通3.2.1 双指针的变体应用快慢指针不仅可以用于数组修改还能解决链表问题// 链表找中点 ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } // slow即为中点左右指针在三数之和中的应用sort(nums.begin(), nums.end()); 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 target) { // 处理结果 while (left right nums[left] nums[left1]) left; while (left right nums[right] nums[right-1]) right--; left; right--; } else if (sum target) left; else right--; } }3.2.2 滑动窗口的优化技巧当窗口性质判断较复杂时可以使用哈希表辅助unordered_mapchar, int freq; int left 0, max_len 0; for (int right 0; right s.size(); right) { freq[s[right]]; while (freq.size() k) { // 窗口内字符种类超过k freq[s[left]]--; if (freq[s[left]] 0) { freq.erase(s[left]); } left; } max_len max(max_len, right - left 1); }对于固定大小窗口的问题可以直接计算int windowSum 0; for (int i 0; i k; i) { windowSum nums[i]; } int maxSum windowSum; for (int i k; i nums.size(); i) { windowSum nums[i] - nums[i - k]; maxSum max(maxSum, windowSum); }3.2.3 前缀和的高级应用前缀和与哈希表结合可以解决更复杂的问题unordered_mapint, int sum_count; sum_count[0] 1; // 初始状态 int preSum 0, count 0; for (int num : nums) { preSum num; if (sum_count.find(preSum - k) ! sum_count.end()) { count sum_count[preSum - k]; } sum_count[preSum]; } return count;二维前缀和的处理vectorvectorint preSum(m 1, vectorint(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { preSum[i][j] matrix[i-1][j-1] preSum[i-1][j] preSum[i][j-1] - preSum[i-1][j-1]; } } // 计算(row1,col1)到(row2,col2)的和 return preSum[row21][col21] - preSum[row1][col21] - preSum[row21][col1] preSum[row1][col1];4. 实战案例分析4.1 移动零LeetCode 283问题描述将数组中的所有0移动到末尾保持非零元素相对顺序。为什么用快慢指针需要原地修改数组需要保持非零元素顺序本质上是要分离满足条件(非零)和不满足条件的元素解决方案void moveZeroes(vectorint nums) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! 0) { swap(nums[slow], nums[fast]); slow; } } }关键点fast指针遍历整个数组slow指针标记下一个非零元素应该放置的位置每次遇到非零元素就与slow位置交换最终slow左侧都是非零元素右侧自然都是零复杂度分析时间复杂度O(n)单次遍历空间复杂度O(1)原地操作4.2 盛最多水的容器LeetCode 11问题描述给定表示高度的数组找出两条线使得它们与x轴构成的容器能容纳最多的水。为什么用左右指针容器的面积由宽度和较小高度决定初始最大宽度时移动较高的一端不可能增加面积只有移动较矮的一端才有可能找到更大面积解决方案int maxArea(vectorint height) { int left 0, right height.size() - 1; int max_area 0; while (left right) { int current_area (right - left) * min(height[left], height[right]); max_area max(max_area, current_area); if (height[left] height[right]) { left; } else { right--; } } return max_area; }优化理解每次移动较矮的一端是因为当前面积受限于较矮的高度移动较高端不会改变限制条件且宽度减小只有移动较矮端才有可能遇到更高的柱子从而可能增加面积复杂度分析时间复杂度O(n)单次遍历空间复杂度O(1)4.3 无重复字符的最长子串LeetCode 3问题描述找出字符串中不含有重复字符的最长子串的长度。为什么用滑动窗口需要找连续子串需要维护无重复字符的窗口窗口性质(字符唯一性)动态变化解决方案int lengthOfLongestSubstring(string s) { unordered_setchar charSet; int left 0, max_len 0; for (int right 0; right s.size(); right) { while (charSet.count(s[right])) { charSet.erase(s[left]); left; } charSet.insert(s[right]); max_len max(max_len, right - left 1); } return max_len; }优化版本使用哈希表记录位置int lengthOfLongestSubstring(string s) { unordered_mapchar, int lastSeen; int left 0, max_len 0; for (int right 0; right s.size(); right) { if (lastSeen.count(s[right]) lastSeen[s[right]] left) { left lastSeen[s[right]] 1; } lastSeen[s[right]] right; max_len max(max_len, right - left 1); } return max_len; }复杂度分析时间复杂度O(n)每个字符最多被处理两次加入和移除空间复杂度O(min(m, n))m为字符集大小4.4 和为K的子数组LeetCode 560问题描述给定整数数组和整数k找到和为k的连续子数组的个数。为什么用前缀和哈希表需要频繁计算子数组和直接枚举所有子数组O(n²)效率低前缀和可以将问题转化为两数之和问题解决方案int subarraySum(vectorint nums, int k) { unordered_mapint, int prefixSumCount; prefixSumCount[0] 1; int currentSum 0, count 0; for (int num : nums) { currentSum num; if (prefixSumCount.find(currentSum - k) ! prefixSumCount.end()) { count prefixSumCount[currentSum - k]; } prefixSumCount[currentSum]; } return count; }关键点理解prefixSumCount记录前缀和出现的次数初始状态和为0出现1次对于每个currentSum查找currentSum - k是否出现过出现的次数即为以当前位置结尾的满足条件的子数组个数复杂度分析时间复杂度O(n)单次遍历空间复杂度O(n)最坏情况下需要存储n个前缀和5. 常见错误与调试技巧5.1 双指针常见陷阱指针移动逻辑错误问题在盛水容器问题中错误地移动较高的一端解决始终移动高度较小的一端示例if (height[left] height[right]) left; else right--;边界条件处理不当问题在快慢指针中未正确处理空数组或单元素情况解决添加前置检查示例if (nums.empty()) return 0;循环条件错误问题使用left right导致中间元素重复处理解决根据问题需求选择或示例回文判断可能需要left right而两数之和用left right5.2 滑动窗口常见问题窗口收缩条件错误问题在无重复字符问题中未及时收缩窗口解决明确窗口不合法条件示例while (charSet.count(s[right]))结果更新时机不当问题在窗口合法前更新结果解决确保在窗口合法后更新示例将max_len更新放在收缩循环之后哈希表维护错误问题未及时更新字符频率表解决在收缩窗口时同步更新示例charSet.erase(s[left]); left;5.3 前缀和易错点前缀和数组大小错误问题忘记前缀和数组比原数组多一位解决vectorint preSum(nums.size() 1, 0);区间和计算下标混淆问题错误使用preSum[r] - preSum[l-1]解决标准写法preSum[r1] - preSum[l]示例计算nums[1..3]的和应为preSum[4] - preSum[1]初始状态遗漏问题忘记初始化prefixSumCount[0] 1解决始终考虑空子数组的情况示例和为k的子数组需要初始状态5.4 调试技巧小数据测试法使用极小的测试案例如空数组、单元素数组快速发现边界错误打印指针位置在循环中打印指针变量值观察移动轨迹cout left: left , right: right endl;可视化窗口内容对于滑动窗口问题打印当前窗口内容cout Window: s.substr(left, right-left1) endl;前缀和验证打印前缀和数组手动验证计算是否正确for (int num : preSum) cout num ;6. 进阶技巧与模式组合6.1 双指针与排序结合许多双指针问题需要先排序sort(nums.begin(), nums.end()); // 然后再应用双指针技巧典型应用三数之和LeetCode 15最接近的三数之和LeetCode 16四数之和LeetCode 186.2 滑动窗口与哈希表结合当窗口性质涉及频率统计时unordered_mapchar, int freq; // 维护窗口内字符频率典型应用最小覆盖子串LeetCode 76找到字符串中所有字母异位词LeetCode 438K个不同整数的子数组LeetCode 9926.3 前缀和与哈希表结合解决子数组和统计问题unordered_mapint, int sumCount; // 记录前缀和出现次数典型应用和为K的子数组LeetCode 560连续的子数组和LeetCode 523统计优美子数组LeetCode 12486.4 多维扩展6.4.1 二维前缀和用于矩阵区域和查询vectorvectorint preSum(m1, vectorint(n1, 0)); // 构建二维前缀和典型题目二维区域和检索 - 矩阵不可变LeetCode 304元素和为目标值的子矩阵数量LeetCode 10746.4.2 滑动窗口变形固定大小窗口问题int windowSum 0; for (int i 0; i k; i) windowSum nums[i]; // 滑动计算典型题目滑动窗口最大值LeetCode 239大小为K的子数组最大和简单变种7. 实战问题分类训练7.1 双指针专项有序数组的两数之和LeetCode 167练习左右指针的基本应用删除排序数组中的重复项LeetCode 26掌握快慢指针原地修改环形链表LeetCode 141理解快慢指针在链表中的应用接雨水LeetCode 42进阶的双指针应用7.2 滑动窗口专项长度最小的子数组LeetCode 209基础窗口大小问题字符串的排列LeetCode 567固定大小窗口应用最大连续1的个数IIILeetCode 1004带容错机制的窗口替换后的最长重复字符LeetCode 424进阶窗口维护技巧7.3 前缀和专项区域和检索 - 数组不可变LeetCode 303基础前缀和应用连续的子数组和LeetCode 523前缀和与模运算结合子数组和整除KLeetCode 974进阶的前缀和统计统计优美子数组LeetCode 1248前缀和与奇偶性结合8. 学习路径建议8.1 入门阶段1-2周掌握三种模式的基本模板熟记快慢指针、左右指针、滑动窗口和前缀和的代码模板完成经典入门题目移动零LeetCode 283盛最多水的容器LeetCode 11无重复字符的最长子串LeetCode 3两数之和 IILeetCode 167重点训练模式识别能力看到题目能快速判断适用哪种模式8.2 巩固阶段2-3周挑战中等难度变种题目三数之和LeetCode 15长度最小的子数组LeetCode 209和为K的子数组LeetCode 560学习模式组合技巧排序双指针滑动窗口哈希表前缀和哈希表开始注意时间/空间复杂度分析对每个解法能准确分析其复杂度8.3 进阶阶段持续练习解决困难级别相关问题最小覆盖子串LeetCode 76滑动窗口最大值LeetCode 239元素和为目标值的子矩阵数量LeetCode 1074参与周赛和虚拟竞赛在时间压力下应用这些模式尝试自创题目变种修改题目条件思考解法如何变化9. 总结与个人心得刷题三年我最大的体会是算法思维比死记硬背重要得多。当初我机械地刷了200道题却收效甚微直到开始注重解题模式的总结水平才有了质的飞跃。关于这三种模式我的实战心得是双指针的精髓在于舍弃无论是盛水容器的移动短板还是有序数组的夹逼核心思想都是通过合理舍弃不可能的解来优化效率。这教会我在解题时先思考哪些部分可以直接排除。滑动窗口的关键是平衡窗口的扩张与收缩需要保持某种平衡条件。我发现很多实际问题都可以抽象为这种平衡维护比如资源分配、流量控制等。前缀和的威力在于转化它将区间查询转化为端点查询把复杂问题转化为简单问题。这种思想在系统设计中也很常见比如预计算、缓存等。建议初学者先把每个模式的5道经典题反复练习直到能闭眼写出bug-free的代码建立自己的解题笔记本记录每个模式的识别信号和变种参加编程社区的每日一题活动保持手感记住刷题不是目的培养算法思维才是。当你看到一个问题能自然想到这可以用滑动窗口解决你就真正掌握了这些技巧。