# LC 1658. Minimum Operations to Reduce X to Zero

### [Problem link](https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/)

###### tags: `leedcode` `medium` `c++` `Sliding Window`

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

Return the **minimum number** of operations to reduce <code>x</code> to **exactly** <code>0</code> if it is possible, otherwise, return <code>-1</code>.

**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:**

- <code>1 <= nums.length <= 10⁵</code>
- <code>1 <= nums[i] <= 10⁴</code>
- <code>1 <= x <= 10⁹</code>

## Solution 1 - Sliding Window
#### C++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = accumulate(nums.begin(), nums.end(), 0) - x;
        if (sum < 0) {
            return -1;
        }
        int longest = -1;
        int cnt = 0;
        int l = 0;
        for (int r = 0; r < nums.size(); r++) {
            cnt += nums[r];
            while (cnt > sum) {
                cnt -= nums[l];
                l++;
            }
            if (cnt == sum) {
                longest = max(longest, r - l + 1);
            }
        }
        return longest == -1 ? -1 : nums.size() - longest;
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
Sol1: 逆向思維 + Sliding Window
[Ref.](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/solutions/2048811/ni-xiang-si-wei-pythonjavacgo-by-endless-b4jt/)
把問題轉換成「從 nums 中移除一個最長的子數組，使得剩餘元素的和為 x」。

換句話說，要從 nums 中找到最長的子數組，其元素和等於 s−x，這裡 s 為 nums 所有元素總和。
由於本題沒有負數，我們可以用滑動窗口, 最後答案為 nums 的長度減去最長子數組的長度。