滑动窗口算法进阶：最大连续 1 与最小操作数

题目描述

给定整数数组 nums 和整数 x。每次操作可以从数组最左端或最右端移除一个元素，使 x 减去该元素的值。返回将 x 恰好减到 0 的最小操作数，无法实现则返回 -1。

逆向思维

从两端取数，等价于保留中间一段连续子数组。如果两端取走的元素和为 x，那么中间剩余的元素和就是 sum(nums) - x。

问题转化为：寻找和为 target = sum - x 的最长子数组。因为总长度固定，中间越长，两端操作数就越少。

算法流程

1. 计算总和 sum，得出目标子数组和 target = sum - x。
2. 若 target < 0，说明总和都不够减，直接返回 -1。
3. 使用滑动窗口寻找和为 target 的最长子数组。
4. 结果即为 n - maxLen。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        int cmp = 0;
        int ret = -1;
        for (auto e : nums) sum += e;
        
        int target = sum - x;
        if (target < 0) return -1;
        
        for (int left = 0, right = 0; right < nums.size(); right++) {
            cmp += nums[right]; // 进窗口
            while (cmp > target) { // 判断
                cmp -= nums[left++]; // 出窗口
            }
            if (cmp == target) ret = max(ret, right - left + 1); // 更新结果
        }
        
        if (ret == -1) return ret;
        else return nums.size() - ret;
    }
};

总结

这两道题展示了滑动窗口的两种常见变体：一种是基于计数约束（如 0 的个数），另一种是基于数值和约束。关键在于根据题意灵活定义窗口的扩张与收缩条件，而不是死记硬背模板。