1658. Minimum Operations to Reduce X to Zero

Minimum Operations to Reduce X to Zero

題目描述：給定整數陣列 nums 和整數 x。每次操作可以從陣列最左端或最右端移除一個元素，並將 x 減去該元素值。求使 x 恰好降為 0 的最少操作次數，若不可能則回傳 -1。

解題思路（等價轉換 + 最長子陣列）：

從兩端刪除若干元素使總和等於 x，等價於保留中間一段連續子陣列，使其總和等於 total - x（total 為陣列總和）。

轉換：

• 若 total < x：不可能，回傳 -1。
• 若 total == x：刪除全部元素，回傳 n。
• 否則，目標 target = total - x，找最長子陣列使其和 = target，答案 = n - 最長子陣列長度。

滑動視窗求最長和為 target 的子陣列：

• 由於 nums 中所有元素均為正整數（保證 1 ≤ nums[i]），視窗內的和隨右指針右移單調不減，隨左指針右移單調不增，因此可用雙指針滑動視窗。
• 維護視窗和 windowSum，當 windowSum > target 時縮小左界；當 windowSum == target 時更新最大長度。

注意：此演算法要求所有元素為正整數，若存在零或負數則需改用前綴和 + 雜湊表。

時間複雜度：O(n) — 雙指針各最多移動 n 次，總操作次數為 O(n)。

空間複雜度：O(1) — 只需常數個輔助變數（total、target、windowSum、l、maxLen），無需額外資料結構。

方法二：前綴和 + 雜湊表

計算前綴和陣列，對每個右端點 r 用雜湊表查詢是否存在左端點 l 使 prefixSum[r] - prefixSum[l] == target。時間 O(n)，空間 O(n)。此方法可處理含零或負數的陣列（滑動視窗在含負數時不適用），但空間較大。

方法三：動態規劃（從兩端）

定義 dpLeft[i] = 從左側刪除恰好 i 個元素的和，dpRight[j] = 從右側刪除恰好 j 個元素的和（用前綴和計算）。枚舉左側刪除數量 i，二分搜尋右側是否有 j 使 dpLeft[i] + dpRight[j] == x，最小化 i + j。時間 O(n log n)，空間 O(n)。比滑動視窗慢但思路直觀。

方法四：遞迴 + 記憶化

定義 dp(l, r, x) = 從子陣列 nums[l..r] 兩端刪除元素使總和 = x 的最少操作數。狀態 O(n²)，轉移 O(1)，總時間 O(n²)，超時但適合理解遞迴結構。

1. 若陣列中含有負整數，滑動視窗不再適用，前綴和 + 雜湊表方法如何正確處理這種情況？需要注意哪些邊界條件？
2. 若允許每次從最左端、最右端或任意中間位置刪除元素，問題變為求子集和，如何用動態規劃解決？時間複雜度如何？
3. 此題「等價轉換為最長中間子陣列」的技巧在 LC 325（最大子數組和等於 k）和 LC 560（和為 k 的子數組數量）中也有體現，三題的核心思路有何共同之處與不同之處？