滑动窗口算法进阶：两道经典题实战

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

逆向思维

从两端取数听起来有点绕，不如换个角度想：

• 如果我们从两端取走的元素和等于 x，那么剩下的中间部分元素和就是 sum(nums) - x。
• 要让操作数最少，意味着取走的元素越少越好，也就是剩下的中间子数组越长越好。

所以问题转化成了：找和为 target = sum - x 的最长子数组。

代码实现

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;
    }
};

这里的关键在于理解 n - maxLen 才是最终的操作次数。如果找不到符合条件的子数组，直接返回 -1。

这两道题展示了滑动窗口的两种典型用法：一种是固定约束（如 0 的个数），另一种是转化目标（如子数组和）。掌握这些模式，面对类似题目时就能快速找到切入点。