LeetCode 1658：将 x 减到 0 的最小操作数（滑动窗口） —— 题解

  👋 欢迎阅读

一.题目

1658. 将 x 减到 0 的最小操作数 – 力扣（LeetCode）

​

🎯 欢迎来到「将 x 减到 0 的最小操作数」题解之旅！ 本文将带你从“从数组两端移除元素使总和恰好为 x”这一逆向思维问题出发，深入理解滑动窗口的巧妙转化，并掌握如何通过寻找最长连续子数组来间接求解最少操作次数。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 1658 题，给定数组 nums 和整数 x，每次只能移除最左或最右的元素，并从 x 中减去该值，求使 x 恰好减为 0 的最少操作数；若无法实现则返回 -1。直接模拟两端移除较复杂，但若逆向思考——保留下来的必定是数组中间的一段连续子数组，其和等于 总和 – x，问题就转化为找最长的连续子数组，使得其和等于 target = sum – x，而最少操作数就是 n – 最长子数组长度。

• 明确学习目标：掌握逆向转化技巧——将“移除两端”转化为“保留中间连续段”，并用滑动窗口在 O(n)O(n) 时间内找到和为目标值的最长子数组。理解为什么“窗口和等于 target”时就是合法解，以及如何通过收缩左边界处理窗口和过大的情况，同时熟练处理边界（如 target < 0 或不存在则返回 -1）。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如 nums = [1,1,4,2,3], x = 5 输出 2）。

本文将从问题转化、逆向构造目标、滑动窗口实现到代码剖析，层层递进。即使你对滑动窗口还不熟悉，我们也会从“移除两端其实就是保留中间”这一核心直觉出发，让你轻松抓住关键思想——最少的操作数对应最长的中间连续子数组，而滑动窗口正是寻找满足固定和的最长窗口的标准工具。现在，让我们一起用逆向思维，把难题转化为熟悉的子数组和问题吧！ 🔄📐

二.做题思路

一、问题分析（前置分析）

每次从数组 最左端或最右端 移除一个元素，并将其值从 x 中减去，直到 x 恰好变为 0。求 最少操作次数。 核心转化（逆向思维）：从两端移除元素，等价于在数组中间 保留一个连续子数组，该子数组的和 = 数组总和 – x。 于是问题变为：在数组中寻找一个和恰好等于 target = sum – x 的最长连续子数组，因为操作次数 = n – 子数组长度，子数组越长，操作越少。 若不存在这样的子数组，或 target < 0，返回 -1。

二、算法策略（滑动窗口）

• 先计算 数组总和 sum1。若 sum1 == x，直接返回 n（移除整个数组）。

• 令 target = sum1 – x，若 target < 0，直接返回 -1。

• 使用 滑动窗口 在数组上寻找 和恰好等于 target 的最长连续子数组：

  • 左右指针 left、right 初始为 0，变量 sum2 记录当前窗口和。

  • 右指针 right 向右扩展，将 nums[right] 加入 sum2。

  • 若 sum2 > target，则 收缩左指针 left，直到 sum2 <= target。

  • 若 sum2 == target，则找到一个有效子数组，更新 最少操作次数 len = min(len, n – (right – left + 1))。

• 遍历结束后，若 len 仍为初始最大值，返回 -1；否则返回 len。

示例执行过程（nums = [1, 1, 4, 2, 3], x = 5，总和 sum1 = 11，target = 6）：

三、正确性说明（简单版本）

逆向转化保证了原问题的解与 寻找和为 target 的连续子数组 等价。滑动窗口 在正数数组上能找到所有和为 target 的连续子数组，因为当窗口和超过目标时，所有正数都只会增加和，所以必须收缩左指针。在窗口和等于目标时，记录当前窗口长度，取最大值。由于我们记录的是 最长 有效子数组长度，所以操作次数 n – 最长长度 就是 最少 操作次数。该策略遍历了所有可能的连续子数组，不会漏解，因此正确。

四、实现细节（边界防护）

• 先计算 总和 sum1，若 sum1 == x 直接返回 n。

• 计算 目标值 target = sum1 – x，若 target < 0 返回 -1。

• 初始化 left = 0，sum2 = 0，len = INT_MAX。

• 使用 for 循环 遍历右指针 right：

  • sum2 += nums[right] 入窗口；

  • 若 sum2 > target，则 收缩左指针：while (sum2 > target && left <= right) { sum2 -= nums[left++]; }

  • 若 sum2 == target，更新 len = min(len, n – (right – left + 1))。

• 注意 while 循环条件 应使用 sum2 > target && left <= right 防止 left 越界（原代码用 left < right，但建议改用更严谨的写法）。

• 若遍历结束后 len == INT_MAX，返回 -1；否则返回 len。

• 时间复杂度 O(n)，空间复杂度 O(1)。

五、返回值（目标映射）

返回 len，即 将 x 减到 0 所需的最少操作数。若无法实现，返回 -1。

三.代码

class Solution
{
public:
int minOperations(vector<int>& nums, int x)
{
// 算法思路：逆向思维
// 题目要求从数组两端移除元素，使得移除的元素之和等于 x。
// 这等价于：在数组中间保留一个连续子数组，其和 = 数组总和 – x。
// 问题转化为：寻找最长连续子数组，使其和为 target = sum – x。
// 然后用数组总长度 n 减去该子数组长度，即为最少操作次数。
// 若 target < 0 或不存在这样的子数组，则返回 -1。

int n = nums.size();

// 1. 计算数组总和 sum1
int sum1 = 0; // 数组所有元素之和
for (int i = 0; i < n; i++)
{
sum1 += nums[i];
}

// 特殊情况：如果整个数组的和正好等于 x，则只需移除整个数组，操作次数为 n
if (sum1 == x)
{
return n;
}

// 如果 x 为负数（题目不会出现，但为健壮性处理），返回 -1
if (x < 0)
{
return -1;
}

// 目标值：需要保留的连续子数组的和
int target = sum1 – x;
int sum2 = 0; // 当前窗口内元素的和
int len = INT_MAX; // 记录最少操作次数（初始化为最大值）
int left = 0, right = 0; // 滑动窗口的左右指针

// 2. 滑动窗口：寻找和为 target 的最长连续子数组
// 右指针不断向右扩展，累加元素到 sum2
for (right = 0; right < n; right++)
{
sum2 += nums[right]; // 入窗口

// 当窗口内和大于 target 时，需要收缩左边界，直到 sum2 <= target
// 注意：left < right 防止 left 越界（当 left == right 且 sum2 > target 时，会先收缩 left）
while (left < right && target < sum2)
{
sum2 -= nums[left]; // 出窗口
left++; // 左指针右移
}

// 如果窗口内和恰好等于 target，则说明找到了一个有效的连续子数组
// 其长度为 right – left + 1，对应的操作次数为 n – 子数组长度
if (target == sum2)
{
// 更新最少操作次数（保留的子数组越长，操作次数越少）
len = min(len, n – (right – left + 1));
}
}

// 3. 如果 len 仍为 INT_MAX，说明不存在和为 target 的子数组，返回 -1
if (len == INT_MAX)
{
return -1;
}
// 否则返回最少操作次数
return len;
}
};

四、易错点分析

难点一：问题转化——为什么用“保留子数组”代替“两端移除”？

int target = sum1 – x;

核心难点： 题目要求从数组两端移除元素，使其和恰好等于 x，求最少操作数。直接模拟两端移除非常复杂。 逆向思维：移除的元素和等于 x，那么未被移除的中间连续部分的和必然等于 sum – x。因此问题转化为：在数组中找到和最接近或恰好等于 target 的连续子数组，且我们想要这个子数组尽可能长（因为剩余要移除的元素数量 = n – 子数组长度，越长操作越少）。 难点在于从“两端取”自然过渡到“中间留”，需要明确理解 target 的含义以及为什么保留子数组越长越好。

难点二：滑动窗口维护的目标——是找“和等于 target”的窗口，而非“不超过 target”

while (left < right && target < sum2)
{
sum2 -= nums[left];
left++;
}
if (target == sum2)
{
len = min(len, n – (right – left + 1));
}

理解上的障碍： 常规滑动窗口通常用于找“和 ≥ target”或“和 ≤ target”的最长/最短子数组。而本代码中，while 收缩条件 target < sum2 只是为了保证窗口和不大于 target，但不会继续收缩到 sum2 < target，因为元素都是正数，一旦 sum2 降到 ≤ target，就可能等于或小于。 关键：收缩后，我们只关心 sum2 == target 的情况，而不关注小于 target 的情况（因为小于 target 无法通过扩大右边界再恢复？实际上，右边界继续扩展后可能再次等于 target）。这要求理解每次右边界固定时，我们通过收缩左边界得到当前右端点下的最小合法窗口（和 ≤ target），然后判断是否恰好等于 target，从而记录有效解。 难点在于区分“收缩过程”和“判断相等”是两个独立步骤，并且 while 条件里用了 target < sum2 而不是 sum2 > target（等价），但隐含了 sum2 可能小于 target 的情况会被保留，等待后续扩展。

难点三：用 min 更新 len 等价于寻找最长保留子数组

len = min(len, n – (right – left + 1));

容易产生的困惑： 初始化 len = INT_MAX，每找到一个和等于 target 的窗口，就计算操作数 n – 窗口长度，并取最小值。 由于 n 是固定的，n – 窗口长度 越小，意味着窗口长度越大。因此多次取最小操作数等价于在所有可行窗口中取最大长度。 难点在于：代码没有显式地维护一个“最大窗口长度”变量，而是直接更新操作数，这需要理解两者之间的等价性。同时，因为滑动窗口可能找到多个重叠窗口，取最小操作数保证了全局最优。

五、流程图

 🎯 闭幕

🎉 恭喜你完成了「将 x 减到 0 的最小操作数」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀 动手实践 在 LeetCode 上提交代码，尝试不同的测试用例。

💡 深入思考

• 本题采用 逆向思维，将“从两端移除元素”转化为 寻找中间连续子数组，使该子数组和为 sum – x。请问 为什么这样转化是等价的？其数学依据是什么？

• 代码中滑动窗口寻找的是 和为 target 的最长连续子数组，而不是直接求最小操作数。为什么最长子数组对应最少操作数？

• 当 target 小于 0 时，直接返回 -1，这是否合理？如果 sum1 == x 时返回 n，这种情况对应什么场景？

• 数组元素均为 正整数，这对滑动窗口的有效性至关重要。如果数组中存在 负数，当前算法还正确吗？为什么？

📚 延伸挑战

• 如果题目要求 输出具体移除的方案（例如最左边移除几个，最右边移除几个），而不是只返回操作次数，你的代码应如何改造以记录方案？

• 如果将问题改为 “将 x 减到 0 的最大操作数”（即尽量多移除元素，但最后仍要恰好减到 0），算法应如何调整？

如果你觉得本文对你有所帮助，欢迎：

👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路

📌 深入思考答案

• 转化依据：数组两端的移除元素之和等于 x，等价于 剩余中间连续部分的元素之和 = 总和 – x。因为移除操作是从两端不断剥离，最后剩下的必然是一个连续子数组，所以原问题转为 找到和为 target 的最长连续子数组。

• 最长子数组对应最少操作数：因为操作数 = 总元素个数 – 保留的子数组长度，保留得越长，移除的元素越少，操作数越少。因此求最长保留长度即可得到最少操作数。

• target < 0 时（即 x > 总和），永远无法减到 0，返回 -1 正确；sum1 == x 时，保留子数组长度为 0（即移除全部元素），操作数为 n，代码直接返回 n 是正确的最优解。

• 存在负数时滑动窗口失效，因为窗口和不再单调（增加负数会减少和），收缩条件 sum2 > target 不再能保证通过左移来调整，必须使用前缀和 + 哈希或双端队列等更复杂方法，因此本题限定正整数是必要的。

🔍 延伸挑战答案

• 挑战1：在滑动窗口找到和为 target 的最长子数组后，记录其起始和结束下标，则移除的左端个数 = 起始下标，右端个数 = n – 结束下标 – 1，即可输出具体方案。

• 挑战2：若要求最大操作数，则需 保留最短的连续子数组（和仍为 target），即求最短的满足和为 target 的连续子数组长度，然后用 n 减去该长度得到最大操作数；只需将求最长改为求最短即可（记录最小长度）。

祝你在 算法之路 上越走越稳，早日攻克每一道难题！下次见 🚀✨