1658. 将 x 减到 0 的最小操作数 Medium
给你两个长度相同的字符串，s 和 t。
给你一个整数数组 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 。
解题思路
输入： 一个整数数组 nums 和一个整数 x
输出： 返回可以将 x 减到 0 的最小操作数，否则返回 -1
本题属于 可变长度滑动窗口类型 类型。
这道题我们可以逆向思维思考：把 从两端取数，使得和为 x 转化为 -> 在中间找到最长的连续子数组，和为 total - x！
这样我们就可以不断的累加遍历到的值，当发现比目标值 total - x 更大时移除最左侧数字继续向右累加
每当累加到目标值后就记录下最长长度
最后将 数组总长度 - 最长长度 就是移除最少的数达到目标值了
代码实现
python
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
# 计算整个数组的总和
total = sum(nums)
# 转换为：找出一个最长的子数组，使得其和为 total - x
target = total - x
# 如果目标小于 0，说明 x 比数组总和还大，不可能实现
if target < 0:
return -1
# 如果目标刚好为 0，说明必须把所有元素都删除
if target == 0:
return len(nums)
# 记录找到的最长子数组的长度（初始为 -1，表示没找到）
maxLen = -1
# 滑动窗口左指针
left = 0
# 当前窗口内的和
currSum = 0
# 遍历数组，作为滑动窗口右边界
for right in range(len(nums)):
currSum += nums[right] # 加入新元素
# 如果当前窗口和大于目标值，缩小窗口（移动左指针）
while currSum > target and left <= right:
currSum -= nums[left]
left += 1
# 如果找到和为 target 的子数组，更新最长长度
if currSum == target:
maxLen = max(maxLen, right - left + 1)
# 如果找到了满足条件的子数组，返回需要删除的次数（总长度减去保留的子数组长度）
return len(nums) - maxLen if maxLen != -1 else -1javascript
/**
* @param {number[]} nums
* @param {number} x
* @return {number}
*/
var minOperations = function(nums, x) {
const total = nums.reduce((acc, curr) => acc + curr, 0);
const target = total - x;
if (target < 0) return -1;
if (target == 0) return nums.length;
let left = 0;
let maxLen = -1;
let currSum = 0;
for (let right = 0; right < nums.length; right++) {
currSum += nums[right];
while (currSum > target && left <= right) {
currSum -= nums[left];
left++;
}
if (currSum === target) {
maxLen = Math.max(maxLen, right - left + 1);
}
}
return maxLen === -1 ? -1 : nums.length - maxLen;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)