題目描述:給定整數陣列 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),無需額外資料結構。
1. Compute total = sum(nums). If total < x: return -1. If total == x: return n. 2. target = total - x. 3. l = 0, windowSum = 0, maxLen = -1. 4. For r in 0..n-1: a. windowSum += nums[r]. b. While windowSum > target: windowSum -= nums[l]; l++. c. If windowSum == target: maxLen = max(maxLen, r - l + 1). 5. Return (maxLen == -1) ? -1 : n - 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²),超時但適合理解遞迴結構。