C++ 力扣 1658.将 x 减到 0 的最小操作数 题解 优选算法 滑动窗口 （同向双指针）优化 每日一题 详细题解

这是封面原图，现在封面放动图不播放了/(ㄒoㄒ)/~~：

一、题目描述

题目链接：将 x 减到 0 的最小操作数

题目描述：

示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：移除后两个元素，4+1=5（或3+2=5），操作数为2。

示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1
解释：无法通过移除元素将4减到0。

示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：移除前三个元素和后两个元素，3+2+20+1+3=30？不，实际是3+2+1+1+3=10，操作数为5。

提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
1 <= x <= 10^9

二、为什么这道题值得你花几分钟看懂？

将 x 减到 0 的最小操作数作为 LeetCode 第 1658 题，是 “逆向思维+滑动窗口” 结合的典型例题。它的核心价值在于：

• 帮你突破“正向解题的思维定式”，理解 “当正向求解复杂时，逆向转化问题” 的解题技巧；
• 强化对 “滑动窗口在寻找特定和的子数组” 场景的应用，掌握“目标值转化”的关键思路；
• 清晰感受 “问题转化对时间复杂度的优化作用”，避免陷入暴力解法的低效陷阱。

学会这道题，你能举一反三解决：

• 长度最小的子数组（LeetCode 209）
• 最长子数组的长度（LeetCode 674）
• 连续子数组的最大和（LeetCode 53）等问题

生活中也有类似场景，比如“从一堆物品的两端取，凑够指定重量的最少取法”“从文章首尾截取段落，凑够指定字数的最短截取次数”，核心都是“正向复杂时，换个角度找最优解”。

三、题目拆解：提取其中的关键点

结合问题要求和代码框架，核心要素如下：

1. 输入是整数数组 nums 和整数 x，数组长度可达 10⁵（需考虑效率）。
2. 操作只能是移除数组最左或最右的元素，且要恰好将 x 减到 0。
3. 需返回最小操作数，无法完成则返回-1。

关键点提炼：

• 操作限制：只能从两端移除元素，不能从中间取，这是正向解题的核心约束。
• 目标特殊性：需“恰好”将x减到0，多减或少减都不满足。
• 效率要求：数组长度达10⁵，暴力解法会超时，需优化到 O(n) 时间复杂度。
• 转化关键：“两端元素和为x”等价于“中间连续子数组和为总元素和-x”，这是解题的突破口。

四、明确思路：从正向困境到逆向滑动窗口

1. 正向暴力解法的困境
最直观的思路是正向枚举所有可能的操作组合：从左端取i个元素、从右端取j个元素，使得取出的元素和为x，求i+j的最小值。

• 枚举版本：
  遍历i（0≤i≤n），计算左端i个元素的和，再从右端开始累加j个元素，直到和为x，记录i+j。时间复杂度 O(n²)，在n=10⁵时会超时。

• 为什么不可行：
  对于长度10⁵的数组，O(n²)意味着10¹⁰次操作，远超计算机处理能力，必然超时。而且枚举过程中容易重复计算，进一步降低效率。

结论：必须换个角度，找到 O(n) 级别的算法。

2. 逆向转化：把“两端取”变成“中间找”

为什么能逆向转化？
假设数组所有元素的总和为sum，要从两端取元素和为x，那么剩下的元素一定是中间连续的子数组，且这个子数组的和为sum - x。

举个例子：
nums = [1,1,4,2,3]，x=5，sum=1+1+4+2+3=11，sum-x=6。
两端取元素和为5时，中间剩下的元素是[4,2]，和为6，正好是sum-x。

因此，问题可以转化为：在数组中找和为target=sum-x的最长连续子数组，该子数组的长度越长，两端需要取的元素就越少（操作数越少）。

滑动窗口的思路

• 先计算数组总和sum，若sum < x，直接返回-1（不可能凑够x）；若sum == x，返回数组长度（需取完所有元素）。
• 定义target = sum - x，若target < 0，返回-1。
• 用滑动窗口找和为target的最长连续子数组：
  • 用left和right标记窗口左右边界，tmp记录窗口内元素和。
  • 移动right扩大窗口，tmp累加元素值；当tmp > target时，移动left缩小窗口，tmp减去元素值。
  • 若tmp == target，记录当前窗口长度，更新最长长度ret。
• 若找到最长子数组，最小操作数为数组长度 - ret；否则返回-1。

为什么这样正确？
因为“两端取元素的和为x”与“中间子数组的和为sum-x”是等价的。中间子数组越长，说明两端需要取的元素越少，操作数就越小。所以找到最长的符合条件的中间子数组，就能得到最小操作数。

滑动窗口遍历一次数组即可找到最长子数组，时间复杂度降至 O(n)。

五、算法实现：逆向滑动窗口

核心逻辑：

1. 计算数组总和sum，判断sum < x则返回-1；计算target = sum - x，若target < 0返回-1。
2. 初始化left=0（窗口左边界）、right=0（窗口右边界）、tmp=0（窗口内元素和）、ret=-1（最长子数组长度）。
3. 移动right扩大窗口，tmp累加nums[right]。
4. 当tmp > target时，移动left缩小窗口，tmp减去nums[left]，left右移。
5. 若tmp == target，更新ret为当前窗口长度与ret的最大值。
6. 遍历结束后，若ret == -1返回-1，否则返回nums.size() - ret。

六、C++代码实现：一步步拆解

完整代码（附详细注释）：

#include <vector>
using namespace std;

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0; // 数组所有元素的总和
        for (auto e : nums) sum += e;
        
        if (sum < x) return -1; // 总和小于x，不可能凑够，直接返回-1
        int target = sum - x; // 转化后的目标：中间子数组的和
        if (target < 0) return -1; // 目标为负，无意义
        
        int ret = -1; // 记录和为target的最长子数组长度
        // 滑动窗口：left左边界，right右边界，tmp窗口内元素和
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {
            tmp += nums[right]; // 右移右边界，元素进窗口
            
            // 当窗口内和超过target，收缩左边界
            while (tmp > target) {
                tmp -= nums[left++]; // 元素出窗口，左边界右移
            }
            
            // 若窗口内和等于target，更新最长长度
            if (tmp == target) {
                ret = max(ret, right - left + 1);
            }
        }
        
        // 若没找到符合条件的子数组，返回-1；否则计算最小操作数
        if (ret == -1) return ret;
        return nums.size() - ret;
    }
};

代码拆解

1. 总和计算与边界判断

int sum = 0;
for (auto e : nums) sum += e;
if (sum < x) return -1; // 总和不够x，直接返回-1
int target = sum - x;
if (target < 0) return -1; // target为负，说明sum < x（其实上面已判断，这里是双重保险）

• sum是数组总元素和，用于转化问题；
• 先做边界判断，避免无效计算：如果总和比x还小，肯定无法凑够，直接返回-1。

2. 滑动窗口初始化

int ret = -1; // 初始为-1，标记未找到符合条件的子数组
int left = 0, right = 0, tmp = 0; // left和right是窗口边界，tmp是窗口内元素和

• ret记录最长子数组长度，找到后才能计算操作数；
• tmp动态维护窗口内元素和，避免重复计算。

3. 窗口扩张与收缩

for (right = 0; right < nums.size(); right++) {
    tmp += nums[right]; // 元素进窗口，扩大窗口
    
    while (tmp > target) { // 窗口内和超过目标，需要收缩
        tmp -= nums[left++]; // 左边界元素出窗口，缩小窗口
    }
    // ... 更新最长长度的逻辑 ...
}

• right从0遍历到数组末尾，确保所有元素都被考虑；
• 当tmp > target时，通过移动left减少窗口内元素和，直到tmp ≤ target，保证窗口始终在有效范围内。

4. 更新最长子数组长度

if (tmp == target) {
    ret = max(ret, right - left + 1);
}

• 当窗口内元素和正好等于target时，计算当前窗口长度（right - left + 1），并更新ret为最大值；
• 只有最长的子数组才能对应最少的操作数，所以要取“最大长度”。

5. 计算最终结果

if (ret == -1) return ret; // 没找到符合条件的子数组，返回-1
return nums.size() - ret; // 总长度减去最长子数组长度，得到最少操作数

• 若ret仍为-1，说明没有中间子数组的和为target，即无法从两端取元素凑够x，返回-1；
• 否则，中间子数组越长，两端需要取的元素越少，操作数就是“总长度-最长子数组长度”。

示例运行过程（以示例1为例）
输入：nums = [1,1,4,2,3]，x = 5

1. 计算sum=1+1+4+2+3=11，target=11-5=6。
2. 初始化left=0，right=0，tmp=0，ret=-1。
3. right=0：tmp=1 ≤6，不等于6 → ret不变。
4. right=1：tmp=1+1=2 ≤6，不等于6 → ret不变。
5. right=2：tmp=2+4=6 ==6 → ret=max(-1, 2-0+1)=3（窗口[0,2]，长度3）。
6. right=3：tmp=6+2=8 >6 → 收缩left：tmp-=nums[0]=1 → tmp=7；left=1 → tmp仍>6；tmp-=nums[1]=1 → tmp=6；left=2。此时tmp=6 ==6 → ret=max(3, 3-2+1)=3（窗口[2,3]，长度2，不比之前长）。
7. right=4：tmp=6+3=9 >6 → 收缩left：tmp-=nums[2]=4 → tmp=5；left=3。tmp=5 ≤6，不等于6 → ret不变。
8. 遍历结束，ret=3。最小操作数=5-3=2 → 符合示例结果。

时间复杂度

• O(n)：right和left都只从0移动到n-1，每个元素最多被访问2次（进窗口和出窗口）。

空间复杂度

• O(1)：仅使用常数个额外变量（sum、target、ret、left、right、tmp），未使用额外空间。

七、实现过程中的坑点总结

1. 忘记判断sum < x的情况

   • 错误：直接计算target=sum-x，若sum <x，target为负，后续滑动窗口无法找到结果，但可能遗漏“直接返回-1”的判断。
   • 解决：先判断sum <x，若成立直接返回-1，避免无效计算。

2. target=0的特殊情况

   • 疑问：当sum=x时，target=0，此时需要找和为0的子数组，最长的就是空数组（长度0）？
   • 解决：target=0时，滑动窗口初始tmp=0，此时tmp == target，ret会被更新为0（窗口[0,0)，长度0），最终操作数= n-0 =n，符合“取完所有元素”的逻辑。

3. 窗口收缩时用if而非while

   • 错误：当tmp > target时，用if (tmp > target)收缩一次left，可能无法让tmp ≤ target（比如一次加入多个大元素）。
   • 解决：必须用while (tmp > target)循环收缩，直到tmp ≤ target，确保窗口有效。

4. 没考虑“找不到符合条件的子数组”的情况

   • 错误：遍历结束后直接返回nums.size() - ret，若ret仍为-1，会得到错误结果。
   • 解决：先判断ret是否为-1，若是则返回-1，否则计算操作数。

八、思考：为什么逆向思维在这里有效？

正向解题时，“从两端取元素”的组合有O(n²)种可能，无法高效枚举；而逆向转化后，“找中间连续子数组”可以用滑动窗口在O(n)时间内解决，核心原因是：

• 正向操作的离散性：两端取元素的组合是不连续的（左端取i个和右端取j个的搭配分散），难以用高效算法覆盖。
• 逆向问题的连续性：中间子数组是连续的，符合滑动窗口“处理连续区间”的适用场景，可通过指针移动动态维护。

当遇到“两端操作”“范围限制”类问题时，若正向枚举复杂，不妨试试：找正向操作的“补集”，将问题转化为连续区间的问题，往往能突破困境。

九、举一反三

掌握本题的“逆向转化+滑动窗口”思路后，可解决以下问题：

• LeetCode 209. 长度最小的子数组：找和≥target的最短子数组，滑动窗口直接应用。
• LeetCode 560. 和为K的子数组：找和为K的子数组个数，虽不能直接用滑动窗口，但“前缀和转化”思路类似。
• LeetCode 1838. 最高频元素的频数：通过逆向思考“需要增加的元素数”，转化为滑动窗口问题。

核心规律：当正向问题涉及“两端/分散操作”时，先计算“总量”，再找“补集的连续区间”，往往能将复杂问题简化为滑动窗口可解的形式。

十、下题预告

明天将讲解 904. 水果成篮，这道题是滑动窗口在“限制元素种类”场景下的经典应用，需要维护窗口内元素的种类不超过2种，感兴趣的小伙伴可以提前思考：如何用滑动窗口统计窗口内的元素种类？当种类超过限制时，如何收缩窗口？

如果觉得这篇解析有帮助，不妨：
🌟 点个赞，让更多人看到这份清晰思路
⭐ 收个藏，下次复习时能快速找回灵感
👀 加个关注，明天见！