1 題目

給你一個整數數組 nums 和一個整數 x 。每一次操作時，你應當移除數組 nums 最左邊或最右邊的元素，然后從 x 中減去該元素的值。請注意，需要 修改 數組以供接下來的操作使用。

如果可以將 x 恰好 減到 0 ，返回 最小操作數 ；否則，返回 -1 。

示例 1：

輸入：nums = [1,1,4,2,3], x = 5
輸出：2
解釋：最佳解決方案是移除后兩個元素，將 x 減到 0 。

示例 2：

輸入：nums = [5,6,7,8,9], x = 4
輸出：-1

示例 3：

輸入：nums = [3,2,20,1,1,3], x = 10
輸出：5
解釋：最佳解決方案是移除后三個元素和前兩個元素（總共 5 次操作），將 x 減到 0 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

2 解答

正難則反，反向思考，求解這個數組中等于 \(sum(nums)-x\)的最長子數組即可。

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        target = sum(nums) - x
        n = len(nums)
        left = 0
        adding = 0
        ans = 0
        dir = 0

        for right , value in enumerate(nums):
            adding += value
            while adding>target and right >= left:
                adding -= nums[left]
                left += 1
            if adding == target:
                dir = 1
                ans = max(ans , right - left + 1)

        return n-ans if dir == 1 else -1