同向双指针滑动窗口算法：最大连续 1 的个数 III、将 x 减到 0 的最小操作数

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

1.3 博主手记

本题整个的思路、算法原理、解题过程建议在纸上推导一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！

012 将 x 减到 0 的最小操作数

力扣链接：1658. 将 x 减到 0 的最小操作数

2.1 题目详解

2.2 算法原理

2.2.1 解法思路：滑动窗口

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

2.2.2 算法流程

1. 转化问题：求 target = sum(nums) - x。如果 target＜0，问题无解;
2. 初始化左右指针 l = 0，r = 0（滑动窗口区间表示为 [ l，r) ，左右区间是否开闭很重要，必须设定与代码一致），记录当前滑动窗口内数组和的变量 sum=0，记录当前满足条件数组的最大区间长度 maxLen = -1；
3. 当小于等于数组长度时，一直循环：

   （1）如果 sum<target，右移右指针，直至变量和大于等于 target，或右指针已经移到头； （2）如果 sum>target，右移左指针，直至变量和小于等于 target，或左指针已经移到头； （3）如果经过前两步的左右移动使得 sum == target，维护满足条件数组的最大长度，并让下个元素进入窗口。

4. 循环结束后，如果 maxLen 的值有意义，则计算结果返回；否则，返回 -1。

2.2.3 代码实现

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：和 sum 区分 
        { 
            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)。

2.3 博主手记

本题整个的思路、算法原理、解题过程建议在纸上推导一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！