将 x 减到 0 的最小操作数（LeetCode）

题目

        给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

        如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

解题

"""
时间复杂度：O(n)，其中 n 是数组的长度。滑动窗口的操作只需要遍历数组一次。
空间复杂度：O(1)，除了输入输出，几乎没有使用额外的空间。
"""


def minOperations(nums, x):
    target = sum(nums) - x
    if target < 0:
        return -1

    if target == 0:
        return len(nums)

    max_len = -1
    current_sum = 0
    left = 0

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum > target:
            current_sum -= nums[left]
            left += 1

        if current_sum == target:
            max_len = max(max_len, right - left + 1)

    return len(nums) - max_len if max_len != -1 else -1


nums = [1, 1, 4, 2, 3]
x = 5
print(minOperations(nums, x))  # 输出: 2