LeetCode 解題筆記：1658. Minimum Operations to Reduce X to Zero

作者：王一哲
日期：2026年9月23日


LeetCode 題目連結：1658. Minimum Operations to Reduce X to Zero

解題想法

中等難度題，題目一個正整數陣列 $nums$ 及一個正整數 $x$，每次操作時可以選擇 $nums$ 最前面或最後面一個數字，將 $x$ 減去這個數字並從 $nums$ 之中移除此項，如果要使 $x$ 歸零，最少的操作次數是幾次？如果無法歸零，回傳 $-1$。這題底下的提示很重要，如果真的按照題目的要求寫程式，要先計算 $nums$ 的前綴和 $psum$ 及後綴和 $ssum$，再從 $psum$ 及 $ssum$ 之中分別檢查使 $x$ 歸零需要取的數量，這樣寫很麻煩。提示中有說，改成計算連續子陣列的和，假設 $nums$ 加總為 $total$，則我們要找的連續子陣列和為 $target = total - x$，如果 $target = 0$ 回傳 $nums$ 的長度 $n$；如果 $target$ 是其它的值，則用滑動視窗找區間和等於 $target$ 的最長子陣列長度 $length$，答案為 $n - length$。

Python 程式碼

Runtime: 71 ms, beats 76.89%. Memory: 30.84 MB, beats 71.36%.

class Solution:
    def minOperations(self, nums: list[int], x: int) -> int:
        n = len(nums)  # 數量
        target = sum(nums) - x  # 最長子陣列和目標值，等於全部的元素加總 - x
        # 特例，如果目標值為 0，全部都要刪掉，回傳 n
        if target == 0: return n  
        
        # 一般狀況，用滑動視窗找加總等於目標值的最長子陣列
        ans = n + 1  # 答案設定成不可能的值 n + 1
        left = 0  # 左端點
        isum = 0  # 區間和
        for right in range(n):  # 掃過右端點 0 ~ n-1
            isum += nums[right]  # 更新區間和
            # 如果左、右端點未重合，區間和大於目標值，移除左端點
            while left < right and isum > target:
                isum -= nums[left]
                left += 1
            # 如果區間和等於目標值，更新答案
            if isum == target:
                length = right - left + 1
                ans = min(ans, n - length)
        # 如果答案不是預設值回傳答案，反之回傳 -1
        return ans if ans < n + 1 else -1

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 102.27 MB, beats 91.82%.

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = (int)nums.size();  // 數量
        int target = accumulate(nums.begin(), nums.end(), 0) - x;  // 最長子陣列和目標值，等於全部的元素加總 - x
        // 特例，如果目標值為 0，全部都要刪掉，回傳 n
        if (target == 0) return n;
        
        // 一般狀況，用滑動視窗找加總等於目標值的最長子陣列
        // 答案設定成不可能的值 n + 1，左端點，區間和
        int ans = n + 1, left = 0, isum = 0;
        for(int right = 0; right < n; right++) {  // 掃過右端點 0 ~ n-1
            isum += nums[right];  // 更新區間和
            // 如果左、右端點未重合，區間和大於目標值，移除左端點
            while(left < right && isum > target) {
                isum -= nums[left];
                left++;
            }
            // 如果區間和等於目標值，更新答案
            if (isum == target) {
                int length = right - left + 1;
                ans = min(ans, n - length);
            }
        }
        // 如果答案不是預設值回傳答案，反之回傳 -1
        return(ans < n + 1 ? ans : -1);
    }
};

C 語言程式碼

Runtime: 2 ms, beats 64.29%. Memory: 17.08 MB, beats 94.64%.

int minOperations(int* nums, int numsSize, int x) {
    int n = numsSize, total = 0;  // 數量
    for(int i = 0; i < n; i++) {
        total += nums[i];
    }
    int target = total - x;  // 最長子陣列和目標值，等於全部的元素加總 - x
    // 特例，如果目標值為 0，全部都要刪掉，回傳 n
    if (target == 0) return n;
    
    // 一般狀況，用滑動視窗找加總等於目標值的最長子陣列
    // 答案設定成不可能的值 n + 1，左端點，區間和
    int ans = n + 1, left = 0, isum = 0;
    for(int right = 0; right < n; right++) {  // 掃過右端點 0 ~ n-1
        isum += nums[right];  // 更新區間和
        // 如果左、右端點未重合，區間和大於目標值，移除左端點
        while(left < right && isum > target) {
            isum -= nums[left];
            left++;
        }
        // 如果區間和等於目標值，更新答案
        if (isum == target) {
            int length = right - left + 1;
            if (n - length < ans) {
                ans = n - length;
            }
        }
    }
    // 如果答案不是預設值回傳答案，反之回傳 -1
    if (ans < n + 1) return ans;
    else return -1;
}