题目
给你一个整数数组
nums
和一个整数x
。每一次操作时,你应当移除数组nums
最左边或最右边的元素,然后从x
中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。如果可以将
x
恰好 减到0
,返回 最小操作数 ;否则,返回-1
。
解题
"""
时间复杂度:O(n),其中 n 是数组的长度。滑动窗口的操作只需要遍历数组一次。
空间复杂度:O(1),除了输入输出,几乎没有使用额外的空间。
"""def minOperations(nums, x):target = sum(nums) - xif target < 0:return -1if target == 0:return len(nums)max_len = -1current_sum = 0left = 0for right in range(len(nums)):current_sum += nums[right]while current_sum > target:current_sum -= nums[left]left += 1if current_sum == target:max_len = max(max_len, right - left + 1)return len(nums) - max_len if max_len != -1 else -1nums = [1, 1, 4, 2, 3]
x = 5
print(minOperations(nums, x)) # 输出: 2