LeetCode 1658. 将 x 减到 0 的最小操作数
目录
题目描述
题意分析
给一个整数数组和一个整数
x。每次操作只能移除数组最左边或最右边的那个元素，并把它的值从x里减掉。要求把x恰好减到 0 所需的最少操作次数，做不到则返回 -1。直接按题面理解，这是一个在「取左端还是取右端」之间做选择的过程，每一步有两种分支，$n$ 步下来是 $2^n$ 条路径。但题目并没有对取的顺序提出任何要求，只关心最终取走了哪些元素、取了多少个——顺序信息是冗余的。剥掉顺序之后，一次合法的操作序列只不过是「从左边拿走一个前缀，从右边拿走一个后缀」，二者不重叠。
于是问题的形状完全变了：被拿走的是一个前缀加一个后缀，剩下的必然是中间一段连续的子数组。设数组总和为
total，被拿走部分的和必须等于x，那么剩下那段的和就必须等于total - x。操作次数等于被拿走的元素个数，也就是 $n$ 减去剩下那段的长度，要让次数最少，就要让剩下那段尽可能长。约束透露的信号有两条。其一，$1 \le nums[i] \le 10^4$，元素严格为正——这意味着一段连续区间的和随着区间两端的伸缩是单调变化的，右端右移一定使和变大，左端右移一定使和变小。其二，$n$ 最大 $10^5$，允许 $O(n)$ 或 $O(n \log n)$，但 $O(n^2)$ 地枚举所有区间会到 $10^{10}$ 级别，不可行。
边界情况：
total - x为负说明整个数组加起来都不够减，返回 -1；total - x恰好为 0 说明必须把整个数组拿光，答案是 $n$，而这种情形下「剩下的段」是空段，容易被求最长子数组的循环漏掉；total - x为正但不存在和恰好等于它的连续子数组时，同样返回 -1。
解法：转化为最长定和子数组
核心思路
最终被移除的一定是“一个前缀 + 一个后缀”，因此未被移除的元素必然构成中间的一段连续子数组。设数组总和为
total，移除元素之和要等于x，等价于保留一段和为target = total - x的子数组。操作数等于
n - 保留长度，所以“最少移除”转化为“寻找和为target的最长连续子数组”。这个等价变换消除了每一步选左还是选右的分支。题目保证所有元素为正数，窗口和随右端扩张只会增大，随左端收缩只会减小，因此可以使用滑动窗口。每轮收缩后维持
sum <= target；若恰好相等，就用当前窗口长度更新最长值。正确性来自互补关系：任意合法移除方案都唯一留下一个和为
target的连续区间；反过来，任意这样的区间，都可通过删除它左侧前缀和右侧后缀实现。选择最长区间就等价于选择最少操作。
解题步骤
- 求
total，令target = total - x。- 若
target < 0，数组总和小于x，直接返回 -1。- 若
target == 0，由于元素全为正，只能保留空区间，答案是删除全部n个元素。- 用
left、right维护窗口，并累加sum。- 当
sum > target时持续右移left并减去离开的元素。- 当
sum == target时更新最长窗口best。- 若始终没有合法窗口返回 -1，否则返回
n - best。例如
nums = [1, 1, 4, 2, 3]、x = 5，总和为 11，目标为 6。最长目标区间是[1, 1, 4]，长度 3，因此只需从右端删除 2、3，共 2 次。
代码实现
class Solution {
public int minOperations(int[] nums, int x) {
long total = 0;
for (int num : nums) {
total += num;
}
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)
}
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)$，只维护窗口边界、窗口和与最长长度。
关键点总结
- “删除两端”常可取补集，转化为“保留中间连续区间”。
- 最小删除数等于数组长度减去最长保留长度，目标和是
total - x。- 滑动窗口成立的关键是元素严格为正；若允许负数，应改用前缀和加哈希表。
target == 0代表保留空区间，需要显式覆盖。- 求和使用
long或int64，避免约束变化或累加时溢出。
易错点总结
- 直接贪心每次删除较大端点没有正确性保证，局部选择可能堵死后续组合。
- 把问题转化成和为
x的子数组；正确目标是未删除部分的和total - x。- 找到第一个目标窗口就返回，可能错过更长窗口，进而得到更多操作。
target < 0时仍启动窗口，会越界或产生无意义结果。- 漏掉
target == 0的空区间，会把“删除全部元素”的合法答案误判为 -1。- 在含负数的变体中照搬滑动窗口，窗口和不再单调，收缩策略会失效。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1423. 可获得的最大点数 | 中等 | 同样是「取两端换成留中间」，但保留段长度固定、要最小化其和 |
| 209. 长度最小的子数组 | 中等 | 目标是「和至少为 target」的最短窗口，收缩时机与本题相反 |
| LCR 008. 长度最小的子数组 | 中等 | 与 209 同题面，适合用来固化「求最短」那一版模板 |
| 713. 乘积小于 K 的子数组 | 中等 | 窗口量从和换成积，统计的是子数组个数而非长度 |
| LCR 009. 乘积小于 K 的子数组 | 中等 | 与 713 同题面，注意 k <= 1 时窗口无法成立的边界 |
| 1004. 最大连续1的个数 III | 中等 | 约束从「和」变成「窗口内 0 的个数不超过 k」 |
| 3. 无重复字符的最长子串 | 中等 | 窗口合法性由哈希集合维护，收缩依据是字符重复 |
| 76. 最小覆盖子串 | 困难 | 合法性是多字符计数全部达标，需要额外维护满足数 |
| 560. 和为 K 的子数组 | 中等 | 允许负数，单调性失效，必须换成前缀和加哈希表 |
| 325. 和等于 k 的最长子数组长度 | 中等 | 本题去掉正数限制后的一般形式，哈希表只记前缀和首次出现位置 |
| 862. 和至少为 K 的最短子数组 | 困难 | 含负数求最短，需要前缀和配单调队列 |