滑动窗口算法实战：两道经典题深度解析

注意这里 left 和 right 都在循环中移动，逻辑非常紧凑。实际运行时，每个元素最多被访问两次，时间复杂度是 O(n)。

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

题目链接： LeetCode 1658

逆向思维转换

这道题稍微绕一点。题目要求从两端取数使总和为 x，求最小操作数。

直接模拟两端取数比较麻烦，不如换个角度想：如果两端取走的和是 x，那中间剩下的部分和就是 总和 - x。为了让操作数最少，也就是取走的元素最少，等价于让中间剩下的子数组最长。

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

算法流程

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

代码实现

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

这里有个细节，只有当窗口和恰好等于 target 时才更新结果。如果遍历完都没找到，说明无法凑成 x，返回 -1。