1658. Minimum Operations to Reduce X to Zero

https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it's possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

• 1 <= nums.length <= 105

• 1 <= nums[i] <= 104

• 1 <= x <= 109

从给定数组左边和右边取连续的数，问最少的取数个数能让和等于x。问题可以转化为找最长子数组使得和为sum - x =>动态窗口。也可以看成左右此消彼长的过程，两个指针先让左边的尽量取直到取到x，之后再从右边开始取，每次取一个数后将左边指针退到左右总和不超过x的位置，以此类推直到右指针往前走完所有可能的位置，是形式稍微特别些的动态窗口。

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        N = len(nums)
        l, r, s, cnt, res = 0, N - 1, 0, 0, float('inf')
        while l < N and s + nums[l] <= x:
            s += nums[l]
            l += 1
            cnt += 1
            if s == x: res = min(res, cnt)
        if l == N and s < x: return -1
        l -= 1
        while r >= 0:
            cnt += 1
            s += nums[r]
            while l >= 0 and s > x:
                cnt -= 1
                s -= nums[l]
                l -= 1
            if s == x: res = min(res, cnt)
            r -= 1
        return -1 if res == float('inf') else res