滑动窗口算法：最大连续 1 的个数 III 与将 x 减到 0 的最小操作数

时间复杂度：O(n)，空间复杂度：O(1)。

将 x 减到 0 的最小操作数

题目描述：

题目详解

算法原理

解法思路：滑动窗口

题目要求的是数组「左端 + 右端」两段连续的、和为 x 的最短数组，信息量稍微多一些，不易理清思路；我们可以转化成求数组内一段连续的、和为 sum(nums) - x 的最长数组。此时，就是熟悉的「滑动窗口」问题了。

相关博客链接： 【优选算法必刷 100 题】第 009~010 题（同向双指针：滑动窗口算法）：长度最小的子数组、无重复字符的最长子串问题求解

算法流程

1. 转化问题：求 target = sum(nums) - x。如果 target＜0，问题无解;
2. 初始化左右指针 l = 0，r = 0（滑动窗口区间表示为 [l，r) ，左右区间是否开闭很重要，必须设定与代码一致），记录当前滑动窗口内数组和的变量 sum=0，记录当前满足条件数组的最大区间长度 maxLen = -1；
3. 当 right 小于等于数组长度时，一直循环：
   • 如果 sum < target，右移右指针，直至变量和大于等于 target，或右指针已经移到头；
   • 如果 sum > target，右移左指针，直至变量和小于等于 target，或左指针已经移到头；
   • 如果经过前两步的左右移动使得 sum == target，维护满足条件数组的最大长度，并让下个元素进入窗口。
4. 循环结束后，如果 maxLen 的值有意义，则计算结果返回；否则，返回 -1。

代码实现

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

时间复杂度：O(n)，空间复杂度：O(1)。

注：本文思路及推导过程建议读者在纸上自行演练一遍，加深理解。