当前位置：首页 > news >正文

12.将 x 减到 0 的最小操作数 | 滑动窗口+正难则反

news 2026/6/1 10:58:29

1. 题目解析

2. 算法原理

2.1 正难则反的转换

2.2 滑动窗口解法

3. 编写代码

4. 总结

1. 题目解析

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

链接：1658. 将 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

（注释：从数组两端移除元素，x 的变化过程，比如示例 1 中移除最后两个元素[2,3]，x 从 5→3→0，共 2 次；另一种尝试移除前两个[1,1]，x 5→4→3，不是最优。）

2. 算法原理

核心思路：正难则反 + 滑动窗口

2.1 正难则反的转换

我们需要让x减到 0，相当于从数组的两端移除元素，使这些元素的和等于x。反过来想：如果我们能找到一个中间子数组，其和为sum - x（sum是数组总和），那么剩下的元素（两端的）就是需要移除的，且移除的数量最少。

设数组总和为sum，目标子数组的和为target = sum - x。
我们需要找到最长的子数组，其和等于target。这样，移除的元素数量（操作数）就是n - len（n是数组长度，len是子数组长度）。

（数组整体和为sum，中间子数组和为target = sum - x，则两端移除的元素和为x。要最小化操作数，即最大化中间子数组的长度len，操作数为n - len。）

2.2 滑动窗口解法

滑动窗口用于找最长子数组和为 target 的情况，步骤如下：

初始化left = 0, right = 0（窗口左右边界），tmp = 0（窗口内元素和）。
右边界right右移，进窗口：tmp += nums[right]。
若tmp > target，则左边界left右移，出窗口：tmp -= nums[left++]，直到tmp <= target。
若tmp == target，更新最大长度ret = Math.max(ret, right - left + 1)。

3. 编写代码

class Solution { public int minOperations(int[] nums, int x) { int sum = 0; for (int a : nums) sum += a; int target = sum - x; // 处理细节：如果target小于0，说明无法通过移除两端元素让x到0 if (target < 0) return -1; int ret = -1; for (int left = 0, right = 0, tmp = 0; right < nums.length; right++) { tmp += nums[right]; // 进窗口 while (tmp > target) { // 判断：窗口和超过target，需要缩小窗口 tmp -= nums[left++]; // 出窗口 } if (tmp == target) { ret = Math.max(ret, right - left + 1); // 更新最长子数组长度 } } if (ret == -1) return ret; // 没找到符合条件的子数组 else return nums.length - ret; // 操作数 = 总长度 - 最长子数组长度 } }