滑动窗口算法实战：最大连续 1 的个数 III 与最小操作数

代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int zero = 0;
        int ret = 0;
        for (int left = 0, right = 0; right < nums.size(); right++) {
            if (nums[right] == 0) zero++; // 进窗口
            while (zero > k) { // 判断
                if (nums[left++] == 0) zero--; // 出窗口
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

2. 1658. 将 x 减到 0 的最小操作数

题目描述

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

示例：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：移除最右端的 3，再移除最右端的 2，x = 5 - 3 - 2 = 0

思路分析

逆向思维 + 滑动窗口

从两端取数 → 等价于找一个中间连续子数组，其和为 total - x。

• 设数组总和为 sum
• 问题转化为：找最长的子数组，使其和为 sum - x
• 最小操作数 = n - 最长子数组长度

为什么？

• 两端取走的元素和 = x
• 剩下中间的元素和 = sum - x
• 操作数最少 → 中间剩余最长

算法流程

1. 计算 target = sum(nums) - x
2. 如果 target < 0，返回 -1（总和都不够减）
3. 滑动窗口找和为 target 的最长子数组
4. 返回 n - maxLen（若 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;
    }
};