滑动窗口——将x减到0的最小的操作数

一.题目描述

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

二.题目解析 

题目还是很简单的，我们只需要每次在数组的左边或者右边选一个数，让x减去它，然后重复这个过程，如果x恰好可以减到0，那么就返回最小的操作次数；如果不能，则返回-1.

需要注意的是：减去了的数就不能再减了。

下面结合示例一来说明：

我们即可以先删除前两个1，然后删除最左边的3，就可以答案目的，此时操作3次；

我们也可以删除最右边的3、2，此时只需要操作两次。

所以最小的操作数就是2.

但是如果这样就写代码的话会非常复杂，我们可以采取"正难则反"的原则来解题。

我们要找到几个数的和是x，且这几个数分布在数组的左右，题目的要求就是在数组左右找到一小块区间，让区间的和为x即可，而且这两个区间的长度要尽可能地小：a+b ==x

那么我们可以将问题转换一下，既然左右的和为x，那么中间的和就等于数组的和tol-x。此时我们的问题就转化为了求一段连续的子区间，要求该子区间的和为tol-x。当我们求出该子区间的长度之后，该题的结果就等于该数组的总长度减去该子区间的长度len。

三.算法原理

1.暴力解法

枚举出所有的子区间，找到其中和为tol-x，且最长的区间。

方法就是先固定一个左端点left，然后枚举右端点，同时求和。找出满足的区间即可。

暴力枚举的时间复杂度为：O(N^2)，空间复杂度为O(1)。

2.滑动窗口

我们借助暴力解法来进行优化：

优化1：当子区间的和大于tol-x的时候，我们就不必继续让right继续++了，因为后面的区间已经不满足条件了，枚举了也是白枚举。我们此时让left++，获得一个新的子区间，判断是否满足要求。

如果满足要求了，left就不用动了。

优化2：当left找到一个新位置之后，right不必重新从left的位置开始，直接从原本的位置继续向右就行了。

为什么呢？ 

因为当前[left,right]区间已经满足要求了即区间和<=tol-x，那么就算你重新从left开始走，依旧会走到那个地方，这是一定的。所以可以直接舍弃到回退的这一步。

综上，left和right两个指针都同时向右走，所以这道题可以用滑动窗口来解决。

滑动窗口步骤：

进窗口：让区间的和加上right当前的元素；

判断：如果区间的和大于target了，此时让最左边的值出窗口，然后继续判断

更新结果：当区间满足条件后，还要进行判断，只有区间和等于target 才需要更新结果。

时间复杂度：O(N)，空间复杂度：O(1).

四.代码实现

这道题还是有很多细节需要处理：当我们的目标值即最长的子区间的和小于0时，说明该区间不存在，即x不可能减小到0，此时返回-1即可。

因为如果不满足题意要返回-1，所以我们可以直接让长度为-1.

int left = 0;
int right = 0;
int tol= 0;//数组的和
for (auto e : nums)
{
    tol+= e;
}
int target = tol- x;//目标值，寻找最长子区间和为target
if (target < 0)
{
    return -1;
}

int sum = 0;
int len = -1;//子区间长度
while (right < nums.size())
{
    sum += nums[right];
    while (sum > target)
    {
        sum -= nums[left++];
    }

    if (sum == target)
    {
        len = max(len, right - left + 1);
    }
    right++;
}
return len == -1 ? -1 : nums.size() - len;