---

[!info] related notes 算法面试题型 MOC 滑动窗口

将x减到0的最小操作数

题目

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

题解

滑动窗口

/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function (nums, x) {
    const n = nums.length;
    let sum = 0;               // 当前窗口（后缀）的和
    let right = n;             // 窗口右端（不含）的位置，初始在数组末尾

    // ① 先尽可能把右侧的元素加入窗口，得到最长的合法后缀
    while (right > 0 && sum + nums[right - 1] <= x) {
        right--;               // 向左扩展后缀
        sum += nums[right];
    }

    // 若已经把所有元素都加入后仍未达到 x，说明不可能
    if (right === 0 && sum < x) return -1;

    // ans 保存当前最小的操作次数
    // 如果仅使用后缀就已经等于 x，则操作数为 n - right（即后缀长度）
    let ans = (sum === x) ? n - right : n + 1;   // n+1 代表“无解”占位

    // ② 从左端逐步加入元素，形成前缀，同时收缩后缀使总和不超过 x
    for (let left = 0; left < n; left++) {
        sum += nums[left];                     // 把左端元素加入窗口

        // 当窗口和 > x 时，右端收缩（去掉最右侧的元素）
        while (right < n && sum > x) {
            sum -= nums[right];
            right++;                           // 窗口右端右移
        }

        // 若此时仍然 > x，说明左端已经太长，后面的循环也不可能满足
        if (sum > x) break;

        // 当窗口和恰好等于 x，更新最小操作数
        if (sum === x) {
            // 已取走的元素数 = 前缀长度 (left+1) + 后缀长度 (n-right)
            ans = Math.min(ans, left + 1 + n - right);
        }
    }

    // 若 ans 仍为初始的 n+1，说明不存在合法方案
    return ans > n ? -1 : ans;
};