給定整數陣列
nums和整數x，每次操作可以從陣列最左邊或最右邊移除一個元素並從 x 中減去該值。回傳使 x 恰好變為 0 的最少操作次數。若無法達成，回傳 -1。
Example:
Input: nums = [1,1,4,2,3], x = 5 Output: 2（移除左邊兩個 [1,1] 或右邊兩個 [2,3]）
Intuition
TIP
核心思路：逆向思考 — 從兩端移除元素和為 x，等價於中間留下一段連續子陣列和為 totalSum - x。問題轉化為找和等於目標值的最長子陣列。
- 直接思考從兩端取元素很複雜（左取幾個、右取幾個的組合）
- 轉化後就是經典的「和等於 target 的最長子陣列」，用滑動視窗即可
- 最長中間子陣列 = 最少操作次數
Approaches
1. Prefix Sum + HashMap — O(n) / O(n)
- Idea: 用 Prefix Sum 找左邊的和，再從右邊找補足的部分
- Time:
O(n) - Space:
O(n)- HashMap
class Solution {
fun minOperations(nums: IntArray, x: Int): Int {
val total = nums.sum()
if (total < x) return -1
if (total == x) return nums.size
// 找左端 prefix sum
val leftSum = mutableMapOf(0 to 0)
var sum = 0
for (i in nums.indices) {
sum += nums[i]
if (sum <= x) leftSum[sum] = i + 1
}
var result = leftSum[x] ?: Int.MAX_VALUE
var rightSum = 0
for (j in nums.indices.reversed()) {
rightSum += nums[j]
if (rightSum > x) break
val need = x - rightSum
if (need in leftSum) {
val leftCount = leftSum[need]!!
if (leftCount <= j) { // 不重疊
result = minOf(result, leftCount + (nums.size - j))
}
}
}
return if (result == Int.MAX_VALUE) -1 else result
}
}⭐ 2. Reverse Sliding Window (longest middle subarray) — O(n) / O(1)
- Idea: 目標 =
totalSum - x，用可變滑動視窗找和等於目標的最長子陣列，答案 =n - maxLen - Time:
O(n)- 一次遍歷 - Space:
O(1)
class Solution {
fun minOperations(nums: IntArray, x: Int): Int {
val target = nums.sum() - x
if (target < 0) return -1
if (target == 0) return nums.size
var left = 0
var windowSum = 0
var maxLen = -1
for (right in nums.indices) {
windowSum += nums[right]
while (windowSum > target) {
windowSum -= nums[left]
left++
}
if (windowSum == target) {
maxLen = maxOf(maxLen, right - left + 1)
}
}
return if (maxLen == -1) -1 else nums.size - maxLen
}
}WARNING
所有元素為正整數，所以視窗和具有單調性（擴大必增、縮小必減），滑動視窗才正確。target < 0 時直接回傳 -1。
🔑 Takeaways
- Pattern: 逆向思考 — 把「兩端最少操作」轉化為「中間最長子陣列」
- Key trick: 「從兩端取」的問題常可轉化為「中間留下」，利用
totalSum - x作為目標值；正數陣列保證滑動視窗的單調性