滑动窗口算法精讲：从LeetCode 1658题掌握最长子数组求解 1. 项目概述从“减到零”到“找最长子数组”的思维跃迁今天我们来啃一道力扣LeetCode上的中等难度题——1658. 将 x 减到 0 的最小操作数。初看题目描述你可能会有点懵给你一个整数数组nums和一个整数x每一次操作你可以从数组的最左边或者最右边移除一个元素并从x中减去这个元素的值。目标是用最少的操作次数将x恰好减到 0。如果无法达成则返回 -1。很多朋友的第一反应是模拟这个过程用递归或者动态规划去尝试所有移除左右元素的组合。这个思路本身没错但复杂度会非常高对于长度可能达到 10^5 的数组来说无疑是死路一条。这道题的精妙之处恰恰在于它要求我们跳出“移除”的固有思维进行一次关键的问题转化。这也是算法题中一个非常重要的技巧当正向思考困难时试试逆向思维。我们不妨这样想从数组两端移除元素使得移除的元素和等于x。那么剩下的、没有被移除的中间部分其元素和是多少没错就是sum(nums) - x。假设整个数组的总和为total我们的目标就变成了在数组nums中找到一个最长的连续子数组使得这个子数组的和等于total - x。为什么是“最长”因为我们要移除的元素是两端的部分移除的元素个数即操作数等于数组总长度减去中间子数组的长度。为了让操作数最小我们就需要让中间剩下的子数组长度最大。所以原问题“最小操作数将 x 减到 0” 被完美等价转化为 “寻找和为total - x的最长子数组长度”。一旦我们找到了这个最长子数组的长度max_len那么答案就是n - max_len如果total - x 0或根本找不到这样的子数组则返回 -1。这个转化是解决本题的核心也是面试中面试官希望看到的洞察力。接下来寻找和为定值的最长子数组就是滑动窗口同向双指针算法的经典战场了。2. 核心思路解析滑动窗口同向双指针的适用场景与原理为什么滑动窗口Sliding Window是解决这个转化后问题的“优选算法”我们需要先理解滑动窗口算法解决的是什么样的问题。滑动窗口算法通常用于处理数组/字符串的连续子区间问题特别是当问题可以归结为“满足某种条件的连续子数组的最大/最小长度”或者“满足条件的子数组个数”时。它的核心思想是维护一个窗口用两个指针left和right表示区间[left, right)或[left, right]通过动态调整左右指针来移动这个窗口从而遍历所有可能的连续子区间但避免了嵌套循环带来的 O(n²) 复杂度。滑动窗口的强大之处在于它通常能将复杂度降至 O(n)。对于本题转化后的目标——“寻找和为target total - x的最长子数组”滑动窗口的工作流程非常直观初始化左右指针left 0,right 0窗口和window_sum 0记录最大长度max_len -1初始化为一个无效值如 -1。不断将右指针right向右移动将nums[right]的值加到window_sum中扩大窗口。在每次右移后检查当前window_sum是否大于target。如果大于说明窗口内的和太大了我们需要收缩窗口左侧即不断将左指针left向右移动并从window_sum中减去nums[left]直到window_sum target。当window_sum不再大于target时我们检查它是否等于target。如果相等恭喜我们找到了一个符合条件的子数组其长度为right - left 1取决于区间定义。我们用这个长度更新max_len。重复步骤 2-4直到右指针right遍历完整个数组。这个过程保证了我们以 O(n) 的时间复杂度考察了所有以right结尾的、和不超过target的子数组并在其中捕捉到了所有和恰好为target的情况同时通过比较长度得到了最大值。这里有一个关键点数组中的元素都是正整数题目虽未明说但力扣的测试用例和常规理解如此若有负数则滑动窗口失效需用前缀和哈希表。正因为是正整数窗口和window_sum随着right右移而单调增加随着left右移而单调减少。这种单调性是滑动窗口能够正确工作的基石它保证了当window_sum target时我们只需移动left就能让它减小而不会错过某些可能性。注意为什么是window_sum target时才收缩因为我们的目标是“等于” target。如果窗口和已经小于 target继续收缩左边界只会让和更小离目标更远没有意义。只有当和超过目标时收缩才有意义是为了尝试让和降下来看能否降到刚好等于 target。3. 代码实现与逐行详解理解了原理我们来看 C 的实现代码。我会提供两个版本的详细注释一个是便于理解的常规版本另一个是简洁优化的版本。3.1 基础清晰版实现class Solution { public: int minOperations(vectorint nums, int x) { int n nums.size(); int total 0; // 计算数组总和 for (int num : nums) { total num; } // 计算需要寻找的子数组目标和 int target total - x; // 边界情况处理 // 1. 如果目标值就是总和意味着需要移除所有元素操作数为 n // 2. 如果目标值小于0说明 x 大于总和不可能完成 if (target 0) return n; if (target 0) return -1; int left 0; // 滑动窗口左边界 int window_sum 0; // 当前窗口内元素的和 int max_len -1; // 记录和为 target 的最长子数组长度初始为-1表示未找到 // 右指针 right 遍历整个数组 for (int right 0; right n; right) { // 将右指针指向的新元素加入窗口和 window_sum nums[right]; // 关键当窗口和超过目标值时收缩左边界 // 因为数组元素为正所以不断移出左侧元素可以减小和 while (left right window_sum target) { window_sum - nums[left]; left; } // 收缩完成后检查当前窗口和是否恰好等于目标值 if (window_sum target) { // 计算当前子数组长度[left, right] 是闭区间长度为 right-left1 int current_len right - left 1; // 更新找到的最大长度 max_len max(max_len, current_len); } // 如果 window_sum target则什么都不做继续扩大右边界 } // 如果找到了符合条件的子数组最小操作数 总长度 - 最长子数组长度 // 如果没找到 (max_len 仍为 -1)则返回 -1 return (max_len ! -1) ? (n - max_len) : -1; } };逐行解读与思考第7-10行计算总和这是转化的第一步。注意这里用了范围 for 循环是 C11 后的现代写法清晰且不易出错。第13-17行边界处理这是写出健壮代码的关键。target 0对应的情况是x total即需要移除所有元素操作数就是n。target 0则意味着即使移除所有元素和也达不到x直接返回 -1。提前处理这些情况可以避免滑动窗口逻辑中的复杂判断。第24行扩大窗口for循环驱动右指针right移动每次将nums[right]加入window_sum。这模拟了考察所有以right结尾的子数组的过程。第27-31行收缩窗口while循环是滑动窗口的核心。条件left right保证了窗口有效左边界不超过右边界。window_sum target是收缩的触发条件。由于元素为正移出左侧元素是减少窗口和的唯一方式。这个循环会持续到窗口和小于等于target。第34-38行检查并更新在窗口和不再大于target后我们检查是否等于。如果等于我们就找到了一个解。计算长度并更新max_len。这里使用max函数来确保记录的是最长长度。第43行返回结果利用三元运算符简洁地返回结果。如果max_len未被更新过仍为 -1说明未找到和为target的子数组返回 -1否则返回n - max_len。这个版本逻辑清晰非常适合理解和面试讲解。时间复杂度是 O(n)因为每个元素最多被左指针和右指针各访问一次。空间复杂度是 O(1)只使用了几个整型变量。3.2 简洁优化版实现在理解了基础版本后我们可以写一个更紧凑的版本思路完全一致但代码行数更少。class Solution { public: int minOperations(vectorint nums, int x) { int total accumulate(nums.begin(), nums.end(), 0); int target total - x; if (target 0) return -1; // 涵盖 target0 的情况吗不需要单独处理。 if (target 0) return nums.size(); // x等于总和需移除所有元素 int n nums.size(); int left 0, window_sum 0, max_len -1; for (int right 0; right n; right) { window_sum nums[right]; while (window_sum target) { window_sum - nums[left]; } if (window_sum target) { max_len max(max_len, right - left 1); } } return max_len ! -1 ? n - max_len : -1; } };优化点解析使用std::accumulate第4行用numeric头文件中的accumulate函数一行代码计算总和比手写循环更简洁、更不易出错体现了对标准库的熟悉。合并边界判断将target 0的判断提前逻辑清晰。但注意target 0的情况必须单独处理因为在滑动窗口循环中如果target为0任何非空窗口的和都大于0max_len将永远无法被更新因为需要window_sum 0只有空窗口和为0但我们的窗口至少包含一个元素最终会错误地返回 -1。所以第6行的判断必不可少。简化while循环条件去掉了left right的判断。因为当left增加到等于right1时window_sum会被减到0因为nums[left]在leftright时被减掉而target是正数所以window_sum (0)不会再大于target循环自然会停止。所以这个条件是冗余的可以省略使代码更简洁。但初学者保留它更有助于理解窗口的合法性。在减法中移动指针第14行window_sum - nums[left]这是一个常见的简洁写法在减去nums[left]的值后立即将left指针加一。它等价于window_sum - nums[left]; left;。两种版本在性能上没有区别简洁版更考验代码熟练度。在面试中我建议先从基础清晰版开始写和面试官讲清楚逻辑如果时间充裕再优化成简洁版这能展示你不同层次的编码能力。4. 算法正确性分析与复杂度证明很多同学写出代码后可能心里还是会打鼓这个滑动窗口算法真的能保证找到最长的、和为target的子数组吗会不会漏掉一些情况我们来做一个严谨的分析。正确性证明 我们的算法遍历了所有可能的右端点right。对于每一个固定的right算法通过收缩左指针left找到了一组left的位置使得窗口[left, right]内的和是不超过target的。具体来说对于当前right算法找到的是满足sum([left, right]) target的最小的left因为一旦和超过target就收缩所以停止时left是满足条件的最靠右的位置即窗口是满足条件的最大的窗口。然后它检查这个窗口的和是否等于target。现在考虑任意一个和为target的子数组[L, R]。当我们的右指针right移动到R时左指针left会如何变化在right到达R之前或之时left一定不会超过L1。为什么因为如果left移动到了L1那么当前窗口是[L1, some_index]其和一定小于等于target因为去掉了正数nums[L]。当right继续移动到R时由于我们只会在和大于target时收缩left而子数组[L, R]的和等于target所以包含L的窗口[L, R]的和不会大于target因此算法不会将left收缩到超过L。换句话说当right R时left一定满足left L。那么当right R且left L时窗口和window_sum是多少它至少包含了[L, R]这个区间因为left Lright R而[L, R]的和是target。由于数组元素都是正数窗口[left, right]的和只会比[L, R]的和更大如果left L则多了[left, L-1]这一段正数和。因此此时window_sum很可能大于target。算法会进入while循环收缩left。在收缩过程中当left被增加到L时窗口恰好变为[L, R]其和等于target。此时while循环的条件window_sum target不再成立因为现在等于了循环停止。紧接着if (window_sum target)条件成立算法就会记录下这个长度为R-L1的子数组。这证明了对于任意一个和为target的子数组我们的算法在右指针扫描到其右端点时一定能够发现它。并且由于我们是在每次发现时更新最大长度max_len所以最终max_len一定是所有满足条件的子数组中的最大长度。因此算法的正确性得证。复杂度分析时间复杂度O(n)其中 n 是数组nums的长度。尽管代码中有一个嵌套的while循环但每个元素最多被左指针left和右指针right各访问一次被right加入窗口一次被left移出窗口一次。因此总操作次数大约是2n是线性复杂度。空间复杂度O(1)。算法只使用了固定数量的额外整数变量total,target,left,right,window_sum,max_len等与输入数组的大小n无关。5. 常见陷阱、变种与相关问题即便理解了算法在实际编码和面试中还是会遇到一些坑。这里我总结几个常见的陷阱和对应的处理方法。陷阱一未处理负数或零我们的滑动窗口解法基于一个重要前提数组元素全部为正整数。这样窗口和才具有随着右指针移动而单调递增的特性。如果题目没有明确说明但测试用例包含非正数负数或零这个算法就会出错。例如数组[1, -1, 2],target2。当窗口为[1, -1]时和为0小于2右指针右移加入2窗口变为[1, -1, 2]和为2符合条件。但更长的子数组[-1, 2]呢其和是1不等于2。我们的算法在right指向最后一个元素时left从0开始和大于2吗1 (-1) 2 2并不大于2所以不会收缩left直接检查相等记录长度3。这似乎没问题但如果target1呢对于子数组[-1, 2]和是1。当right指向2时窗口和是1 (-1) 2 2大于1于是开始收缩left。left0时减去1窗口和变成(-1)21等于target记录长度2。看起来也对其实这里存在隐患。负数的存在破坏了“收缩左边界一定能减小窗口和”的单调性。例如如果数组开头是一个绝对值很大的负数收缩左边界时窗口和可能反而增大。因此标准的同向双指针滑动窗口仅适用于元素非负的情况。如果题目可能包含负数则需要使用“前缀和 哈希表”的方法来寻找和为定值的子数组其时间复杂度也是 O(n)。实操心得在力扣做题或面试时一定要先确认数据的范围。如果题目描述或约束条件中说明了1 nums[i] 10^4之类的就可以放心使用滑动窗口。如果没说或者明确有负数就要换思路。陷阱二目标值 target 为 0 或负数的边界情况正如我们代码中处理的当target total - x小于 0 时直接返回 -1。当target 0时意味着我们需要找一个和为0的子数组。在元素全为正的情况下只有空数组的和为0。但我们的滑动窗口至少包含一个元素left right且每次right移动都会加入元素所以永远找不到window_sum 0的情况max_len不会被更新。因此必须单独处理返回n移除所有元素。这是一个非常关键的边界条件很容易遗漏导致返回错误的 -1。变种与相关问题掌握这道题的核心转化思想“两端移除”转化为“寻找中间最长子数组”和滑动窗口技巧后你可以解决一系列类似问题LeetCode 209. 长度最小的子数组寻找和大于等于target的长度最小的连续子数组。这是滑动窗口最经典的入门题。LeetCode 3. 无重复字符的最长子串寻找不包含重复字符的最长子串。这里窗口收缩的条件是“出现重复字符”。LeetCode 76. 最小覆盖子串在字符串s中找出包含字符串t所有字符的最短子串。难度升级需要配合哈希表记录字符需求。LeetCode 904. 水果成篮寻找最多包含两种“类型”的最长连续子数组。窗口收缩条件是“类型数超过2”。LeetCode 930. 和相同的二元子数组寻找和为goal的子数组个数。这题就和本题非常像了但要求的是个数而不是最长长度。解法可以是滑动窗口对于全非负数组或者前缀和哈希表。对比滑动窗口 vs. 前缀和哈希表对于“和为定值的子数组”问题有两种主流 O(n) 解法滑动窗口适用于数组元素非负。它擅长解决“最长/最短”长度问题因为双指针可以动态维护一个连续区间。前缀和哈希表适用于元素有正有负的通用情况。它通过计算前缀和prefix_sum[i]并利用哈希表快速查找是否存在一个之前的前缀和prefix_sum[j]使得prefix_sum[i] - prefix_sum[j] target。这种方法更通用但通常用于解决“是否存在”或“有多少个”的问题要直接求“最长”需要额外记录索引信息。对于本题在元素非负的前提下滑动窗口是更优解因为它空间复杂度为 O(1)且代码直观。如果元素可能为负则应采用前缀和哈希表方法其核心代码如下思路int target total - x; if (target 0) return -1; unordered_mapint, int prefix_map; // 记录前缀和 - 最早出现的索引 prefix_map[0] -1; // 重要前缀和为0出现在索引-1处即一个元素都不取 int prefix_sum 0; int max_len -1; for (int i 0; i n; i) { prefix_sum nums[i]; // 我们需要找 prefix_sum - target 是否出现过 if (prefix_map.count(prefix_sum - target)) { int len i - prefix_map[prefix_sum - target]; max_len max(max_len, len); } // 只记录前缀和第一次出现的位置以保证找到的子数组是最长的 // 不这里有个细节。为了找最长的子数组我们应该记录每个前缀和最早出现的索引。 // 因为当同一个前缀和再次出现时用更早的索引计算出的子数组长度更长。 if (!prefix_map.count(prefix_sum)) { prefix_map[prefix_sum] i; } } return (max_len ! -1) ? n - max_len : -1;注意在这个通用解法中我们通过哈希表prefix_map记录每个前缀和值第一次出现的下标。当遍历到位置i时当前前缀和是prefix_sum我们想找之前某个位置j使得prefix_sum - prefix_sum_j target即prefix_sum_j prefix_sum - target。如果这个值在哈希表中存在说明我们找到了一个子数组[j1, i]的和为target。由于我们记录的是最早的下标这样计算出的长度i - j就是以 i 结尾的、和为 target 的最长子数组长度。遍历所有i并更新max_len即可得到全局最长。这个解法同样能处理target 0的情况寻找prefix_sum - 0即prefix_sum是否出现过。