1658.将 x 减到 0 的最小操作数：哈希表(+前缀和) / 滑动窗口

【LetMeFly】1658.将 x 减到 0 的最小操作数：哈希表(+前缀和) / 滑动窗口

力扣题目链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/

给你一个整数数组 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

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

解题方法一：哈希表+前缀和

正序遍历一遍数组，将sum(nums[0..i]) -> i存入哈希表。

倒序遍历一遍数组，记录遍历过程中的后缀和$cnt$。如果$x-cnt$在哈希表中，则找到一个可行的移除方法。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

AC代码

C++

/*
 * @LastEditTime: 2026-09-23 18:40:09
 */
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        unordered_map<int, int> prefix;
        for (int i = 0, cnt = 0, n = nums.size(); i < n && cnt < x; i++) {
            cnt += nums[i];
            prefix[cnt] = i;
        }
        prefix[0] = -1;
        int ans = prefix.count(x) ? prefix[x] + 1 : nums.size() + 1;
        for (int n = nums.size(), i = n - 1, cnt = 0; i >= 0 && cnt < x; i--) {
            cnt += nums[i];
            if (prefix.count(x - cnt)) {
                ans = min(ans, prefix[x - cnt] + n - i + 1);
            }
        }
        return ans > nums.size() ? -1 : ans;
    }
};

解题方法二：滑动窗口

移除前后缀共计$x$，即使得剩余数组和为$sum-x$。

滑动窗口，每次右边加入窗口一元素，当窗口中元素和大于$sum-x$时不断移除左边元素。若移除结束后窗口中元素和等于$sum-x$，则更新答案。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-09-23 18:48:44
 */
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int allVal = accumulate(nums.begin(), nums.end(), 0);
        x = allVal - x;
        if (x < 0) {  // 不然while会下标越界
            return -1;
        }
        int ans = 10000000;
        for (int l = 0, r = 0, n = nums.size(), cnt = 0; r < n; r++) {
            cnt += nums[r];
            while (cnt > x) {
                cnt -= nums[l++];
            }
            if (cnt == x) {
                ans = min(ans, n - (r - l + 1));
            }
        }
        return ans == 10000000 ? -1 : ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源