LeetCode 1658. 将 x 减到 0 的最小操作数
题目描述
题意分析
每次从当前数组的最左端或最右端移除一个元素，并从
x中减去这个元素值，求把x恰好减为零的最少操作数。如果无法恰好凑出被移除的总和，返回-1。只能从两端取，不能跳过中间元素；一次操作只删除一个。题目描述中的修改数组表示后续只能继续操作剩余部分，本题返回操作次数，不要求实现一定实际搬移数组。所有元素都为正整数，减过头后不可能再通过后续操作恢复为零。
解法：转化为最长定和子数组
核心思路
[!blue]
无论交替删除的顺序如何，最后移除的总是原数组的一段前缀和一段后缀，未删除部分必然是连续的中间区间。反过来，保留任何一段连续区间，都可以通过依次删掉它左边和右边的元素实现。因此可以把问题从“怎样删除两端”改成“保留哪一段中间区间”。
设数组总和为
total，被删除部分要等于x，保留部分就必须等于target = total - x。若保留长度为len，操作数就是n - len；最少操作等价于寻找和恰好为target的最长连续子数组。target < 0表示所有元素都删掉仍不够，直接无解；target == 0时，正数数组只能保留空区间，必须删除全部元素。对正的保留目标，用滑动窗口维护
[left, right]及其和sum。右端加入一个元素会让和增加；当和超过目标时，就不断移出左端，直到不再超过。此时若恰好等于目标，就记录保留长度；若小于目标，则应继续扩张右端，因为再缩左端只会使和更小。左指针不需要回退。一个左端被移走时，原窗口和已经大于目标；以后右端只会加入更多正数，固定这个旧左端的任何更长窗口仍会超标，所以它不可能成为未来答案。对于当前右端，收缩到不超标后，更靠右的左端只会减少和，因此只检查当前窗口就不会漏掉和相等的候选。
用
best = -1区分“尚未找到保留区间”与合法长度。找到一次后不能提前结束，还要搜索其他位置可能更长的保留段；最终返回n - best。整个转换只读取原数组，不必实际执行每次删除。
解题步骤
- 累加数组总和，计算保留目标
target = total - x。- 目标为负时返回
-1，为零时返回数组长度；剩下只处理正目标。- 初始化左端、窗口和与
best = -1，右端依次向右加入元素。- 当窗口和大于目标时，连续移出左端元素，直到窗口和不再超过目标。
- 窗口和恰好等于目标时，用当前长度更新
best，继续扫描其他位置。- 最后若
best未更新则返回-1，否则返回数组长度减去最长保留长度。
代码实现
class Solution {
public int minOperations(int[] nums, int x) {
long total = 0;
for (int num : nums) {
total += num;
}
// 删除两端等价于保留中间，目标改为总和减 x
long target = total - x;
if (target < 0) {
return -1;
}
// 全为正数时零和只能保留空段，因此删除全部
if (target == 0) {
return nums.length;
}
int left = 0;
int best = -1;
long sum = 0;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
// 正数保证缩左端能降低和，每个指针都无需回退
while (sum > target) {
sum -= nums[left++];
}
if (sum == target) {
best = Math.max(best, right - left + 1);
}
}
return best == -1 ? -1 : nums.length - best;
}
}
func minOperations(nums []int, x int) int {
var total int64
for _, num := range nums {
total += int64(num)
}
// 删除两端等价于保留中间，目标改为总和减 x
target := total - int64(x)
if target < 0 {
return -1
}
// 全为正数时零和只能保留空段，因此删除全部
if target == 0 {
return len(nums)
}
left, best := 0, -1
var sum int64
for right, num := range nums {
sum += int64(num)
// 正数保证缩左端能降低和，每个指针都无需回退
for sum > target {
sum -= int64(nums[left])
left++
}
if sum == target && right-left+1 > best {
best = right - left + 1
}
}
if best == -1 {
return -1
}
return len(nums) - best
}
复杂度分析
- 时间复杂度：$O(n)$，先求一次总和，滑动窗口中每个元素再至多加入、移出各一次。
- 空间复杂度：$O(1)$，只使用总和、窗口边界、窗口和与最长长度等固定变量。
关键点总结
[!green]
- 两端删除与中间连续保留一一对应，优化删除数量可以改为最大化保留长度。
- 保留目标是
total - x，不能直接在中间查找删除总和x。- 正数保证超标左端可以永久舍弃，也保证零目标只对应空保留区间。
- 不模拟删除过程，直接计算最长可保留区间，就能避免枚举左右操作顺序。
易错点总结
[!yellow]
- 查找和为
x的中间区间，找到了错误的补集，不能据此计算两端删除次数。- 把目标为零当成没有合法非空窗口而返回失败，会漏掉恰好删除全部元素的情况。
- 每次只收缩一次，窗口仍可能超标，需要连续收缩到不超过目标。
- 用和大于等于目标作为收缩条件，会先移走本可记录的等和窗口；本题只在严格超标时收缩。
- 找到第一个可保留窗口就返回，可能错过更长窗口对应的更少删除次数。
- 每次贪心删除两端中较大的值，不能保证最终恰好凑出目标，更不能保证删除次数最少。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 325. 和等于 k 的最长子数组长度 | 中等 | 删去两端后保留中间最长、和为total-x的区间，可直接转成长目标和子数组。 |
| 1423. 可获得的最大点数 | 中等 | 同样通过两端选择与中间补集互换，本题固定删除和并最小化操作数，原题固定操作数并最大化得分。 |