1658. 将 x 减到 0 的最小操作数

题目链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/

我的思路

典型的双指针/滑动窗口类型题目，想到初始化左右两个指针$l=0, r=n-1$，$n$为所给数组的长度，因为我们要找的是最小操作数，那么在判断左右两边到底减哪个时，采用贪心策略，选更大的那一个，就能让$x$减的更快，更快到0，有几种情况：

1. $nums[l]>nums[r]$:

   1. $nums[l]\leq x$: 说明此时$nums[l]$可以作为一个操作数，$x-nums[l]$，同时操作数$ans+1$，左指针右移$l+1$
   2. $nums[l]>x\geq nums[r]$：则$x-nums[r]$，同样$ans+1$，右指针左移$r-1$
   3. $nums[r]>x$：说明中断了，不再满足题目中的条件，直接break

2. $nums[l]\leq nums[r]$:

   1. $nums[r]\leq x$：$x-nums[r], ans+1, r-1$
   2. $nums[r]>x\geq nums[l]$：$x-nums[l], ans+1, l + 1$
   3. $nums[l]>x$：break

初始化的$ans=0$，循环条件为$l\leq r,x>0$，当循环跳出后，如果$x\neq0$，则返回-1，反之返回$ans$

纠正

这个思路看上去很正确，但实际上考虑得并不周全。采用“从两端贪心减x”的策略，这是一种局部决策法。贪心策略失败的根本原因在于：

• 每次“取较大的一端”并不能保证最终组合的和恰好为 x；
• 局部选择（谁大取谁）可能导致后续无解；
• 问题的全局约束是前缀+后缀的组合，而不是连续的减法过程；

直观来看，比如下面这个步骤：

贪心能保证局部最优解，但可能会因此掠过全局最优解的进入条件，使得解法陷入到一个死局，本来左边的数一直可以减下去使得$x$最终减到0，尽管这样操作数会变多，但能够实现最终的目的，贪心时可能右边会减掉一个很大的数，导致左边无法再进入后续解中，看似找到了最优实则掉进了陷阱，因此需要用“滑动窗口”或“前缀和”在整个数组范围内找到最优区间，而不能局部决策

采用逆向思维，正难则反，题目中说要移除$nums$最左边或最右边的元素，那么剩下的元素是什么呢？其实是$nums$的一个连续子数组，因为左右两边去除的元素之和为$x$，那么剩下的这个子数组中的元素和就应该为$\mathrm{sum}(nums)-x$，那么问题就转化为了我们要找到和为这个数的一个最长子数组（去掉两边的元素数最少，那么中间剩下的要最长，因此是最长子数组）

初始化$l=0,target=\mathrm{sum}(nums)-x,ans=-1$，如果$target<0$，那么说明$nums$的所有元素还不够$x$来减的，直接返回-1，接着用enumerate枚举$nums$中的$r,y$，定义一个中间变量$s$，初始化为0，每次枚举时$s+y$，当$s>target$时，说明当前$[l,r]$包含了我们所要的子数组，此时移动左指针缩短窗口（用while循环来实现判断），当$s=target$时，记录下此时的窗口长度，和之前的相比，如果这个长度更大，就更新$ans$，最终返回$n-ans$，因为我们实际要求的还是两边元素的减少个数，因此要做个减法

反思

1. 为什么$ans$要初始化为-1呢，因为有可能我们要把所有的元素都用上，即这个子数组的长度为0，如果初始化为0，那么我们无法判断是否真正存在符合要求的子数组，在不符合的情况下我们应该返回-1

结果

时间复杂度：$O(N)$

空间复杂度：$O(1)$

已是最优解