1658. Minimum Operations to Reduce X to Zero

Medium
Description

給定整數陣列 nums 和整數 x，每次操作可以從陣列最左邊或最右邊移除一個元素並從 x 中減去該值。回傳使 x 恰好變為 0 的最少操作次數。若無法達成，回傳 -1。

Example:

Input: nums = [1,1,4,2,3], x = 5 Output: 2（移除左邊兩個 [1,1] 或右邊兩個 [2,3]）

Intuition#

核心思路：逆向思考 – 從兩端移除元素和為 x，等價於中間留下一段連續子陣列和為 totalSum - x。問題轉化為找和等於目標值的最長子陣列。

  • 直接思考從兩端取元素很複雜（左取幾個、右取幾個的組合）
  • 轉化後就是經典的「和等於 target 的最長子陣列」，用滑動視窗即可
  • 最長中間子陣列 = 最少操作次數

Approaches#

1: Prefix Sum + HashMap#

  • 概念: 用 Prefix Sum 找左邊的和，再從右邊找補足的部分
  • 時間複雜度: O(n)
  • 空間複雜度: 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: 逆向 Sliding Window（找最長中間子陣列）#

  • 概念: 目標 = totalSum - x，用可變滑動視窗找和等於目標的最長子陣列，答案 = n - maxLen
  • 時間複雜度: O(n) - 一次遍歷
  • 空間複雜度: 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
    }
}

所有元素為正整數，所以視窗和具有單調性（擴大必增、縮小必減），滑動視窗才正確。target < 0 時直接回傳 -1。

🔑 Takeaways#

  • Pattern: 逆向思考 – 把「兩端最少操作」轉化為「中間最長子陣列」
  • 關鍵技巧: 「從兩端取」的問題常可轉化為「中間留下」，利用 totalSum - x 作為目標值；正數陣列保證滑動視窗的單調性