滑动窗口练习4-将x减到0的最小操作数

题目链接：**. - 力扣（LeetCode）**（字节跳动）

题目描述：

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

• 1 <= nums.length <= 105

• 1 <= nums[i] <= 104

• 1 <= x <= 109

提示：正难则反

解法（滑动窗口）：

算法思路：

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

算法流程：

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

class Solution {
public:int minOperations(vector<int>& nums, int x) {int n  = nums.size();int sum = 0;int maxlen = 0;int all = 0;for(int i = 0; i < n; i++){all += nums[i];}int target = all - x;//最长子数组目标值//处理细节if(target < 0) return -1;if(target == 0) return n;for(int left = 0, right = 0; right < n; right++){//进窗口sum += nums[right];while(sum > target){//判断sum -= nums[left++];//出窗口}//更新结果if(sum == target){maxlen = max(right - left + 1, maxlen);}}int ret = n - maxlen == n ? -1 :n - maxlen;return ret;}
};