題目鏈接

將x減到0的最小操作數

題目描述

題目解析

問題重述

給定一個整數數組?nums?和一個整數?x，每次只能從數組的左端或右端移除一個元素，并將該元素的值從?x?中減去。我們需要找到將?x?恰好減為 0 的最少操作次數，如果不可能則返回 -1。

核心思路：轉化問題（逆向思維）

直接求解 "最少移除次數" 比較困難，但我們可以通過逆向思維轉化問題：

• 設數組所有元素的總和為?total
• 要移除的元素總和為?x，意味著剩余未移除的元素總和為?total - x
• 剩余元素必須是連續的中間子數組（因為只能從兩端移除元素）
• 問題轉化為：找到總和為?target = total - x?的最長連續子數組
• 最少移除次數 = 數組總長度 - 最長符合條件的子數組長度

關鍵邏輯解析

• 為什么找最長子數組？
  因為剩余的子數組越長，意味著需要移除的元素越少，操作次數也就越少。

• 邊界情況處理

  • 當?target = 0?時：意味著需要移除所有元素，此時最長子數組長度為 0，操作次數為?n
  • 當?total < x?時：直接返回 -1，因為即使移除所有元素也無法使 x 減為 0

示例演示

以?nums = [1,1,4,2,3]，x = 5?為例：

1. 總和?tmp = 1+1+4+2+3 = 11，target = 11-5 = 6
2. 尋找總和為 6 的最長子數組：[1,1,4]（長度 3）
3. 最少操作次數 = 5 - 3 = 2（移除最后兩個元素 2 和 3）

這種轉化問題的思路非常巧妙，將原本復雜的兩端移除問題轉化為了更簡單的中間子數組查找問題，大大提高了求解效率。

時間和空間復雜度

• 時間復雜度：O (n)，每個元素最多被左右指針各訪問一次
• 空間復雜度：O (1)，只使用了常數額外空間