題目出處
1658. Minimum Operations to Reduce X to Zero
難度
medium
題目分類
Array, Hash Table, Binary Search, Sliding Window, Prefix Sum
2026-09-24 一刷
個人範例程式碼 - 一刷 (2026/09/24)
class Solution:
def minOperations(self, nums: list[int], x: int) -> int:
# reverse the nums, then find the longest window = sum(nums) - x
# the longest window -> the min operations
target = sum(nums) - x
if target < 0: # x more than total sum
return -1
if target == 0: # sum(nums) = x
return len(nums)
left = 0
sum_in_window = 0
best_longest_window = -1
for right in range(len(nums)):
sum_in_window += nums[right]
while left <= right and sum_in_window > target:
sum_in_window -= nums[left]
left += 1
if sum_in_window == target:
best_longest_window = max(best_longest_window, right - left + 1)
return -1 if best_longest_window == -1 else len(nums) - best_longest_window
算法說明
難的在於想到這個是 the longest sliding window 的變化題，
具體來說是原題目是「去頭去尾，找出去掉最少」轉換為「找到中間 window 段落，找出保留最多」
剩下就很容易照著 sliding windows 的邏輯下去解（比起處理去頭、去尾，只需要處理連續的中間更好處理。）
具體的思維轉換為：
- x 轉換為 sum(nums) - x
- 最少 operation 轉換為 求最長的 windows
- 最後答案記得再轉換為 len(nums) - best_longest_window (也有可能不存在，記得處理 -1)
細節補充：left < right 的等於寫不寫不影響結果，
- 差別在於如果 left <= right，
left 會有機會因 left+1 而暫時比 right 大，等於說暫時會允許 windows 全空
(且因為另外一個條件 sum > target)，可預期當前的 nums[right] (也是 nums[left]) 都比 target 大- 如果是 left < right，window 最少會保留 nums[right]，也就是永遠保持 left < right，left 最多剛好等於 right，不會超過
Time Complexity
O(n)
Space Complexity
O(1)