滑动窗口-1658.将x减到0的最小操作数-力扣(LeetCode)

一、题目解析

我们需要移动左边或右边的数使x变为0的操作次数最小，可以结合示例来体会该题运行的逻辑。

结合实例和题目，我们发现需要控制左边的数或右边的数，还需要注意返回-1的情况。这时跟着题目给出的方式控制左右的数无疑是困难的。“正难则反”的思想可以很好的帮助我们解决遇到的难题。接下来让我们再次分析，该如何实现“正难则反” 。

二、算法解析

通过示例1我们能抽象出一幅图

我们要计算的是x(=a+b)的最短长度 ,x不好求，图中的sum-x求解明显比x方便。通过示例1抽象的图，我们由求解x的最短长度转变为求解target(sum-x)的最大长度，降低正面解题的难度。

由示例2我们可以知道a或b是能等于0的，所以我们只需要从左到右找出一段最长的target即可。

暴力解法：滑动窗口枚举出最长的子数组

定义双指针left和right(由于它们同向移动，left和right像一个窗口一样，这就是滑动窗口的由来)，我们需要sum1用于遍历数组计算所有元素的和，用于计算target，用sum记录最长子数组的和。

当right恰好到达某位置时，sum>target，而right后面存在一定小于target的区间，当找到>target时，不需要向后移动right，且向前移动left只会比target更小，所以right是留在原地或者向右移动的。

我们固定left移动right的过程我们叫做进窗口，在窗口了我们还需要做判断，判断sum是否大于target，大于我们就需要出窗口，即left向右移动，这时我们还需要一个len用于记录子数组的最大长度，由于需要返回-1，所以我们可以将len赋值为-1，最后输出结果是判断，如果len == -1，则说明没有最大子数组，返回-1，若结果不为-1，则返回与数组长度的差值。len用于更新结果，当sum==target时我们可以更新len的值。

老规矩，照着上面的思路自己去先思考尝试一下，毕竟有些坑是需要自己试出来滴。

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

三、代码示例

其中呢有两个小坑，其一是target的值，我们默认target是正数，但测试样例中正好出现target为负数的情况，所以这是我们分析时没有想到的一点；其二则是判断条件那里的left<nums.size()，这是被同一个测试样例卡住两次，这次比前一次严重。{1,1}这时还没有对target<0做处理，根据我们的判断sum>target,target此时为-1，循环开始，我们要出窗口,所以left向右移动，这时sum的值为0(进窗口加1后出窗口又减一)，循环继续，这时出窗口后left再次移动，但是由于只有两个元素，所以此时left越界访问直接报错。(ps：小编后来发现在处理target<0情况后，也就不会进入循环，也就不会越界访问了，所以其二的left<nums.size()不加也能通过)

虽然有循环嵌套，但是我们的时间复杂度仍然是O(N)这个级别的(0ms也是小编多次提交才得到的，如果不是0ms也不必慌张)。

看到这里了，如果对您能有所帮助，还请留下一个免费的赞，我们下期再见！