# Question

Formatted question description: https://leetcode.ca/all/1658.html

 1658. 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


# Algorithm - prefix sum

The idea is the prefix sum. First, let’s deal with the target value x, because the question is actually a certain sub-array in the middle of the array that satisfies its array and = the sum of all numbers in the array-some numbers on both sides, so we first set the target value as -x, so when When we use the idea of ​​prefix sum to find a sub-array that meets the requirements, this sub-array is already equal to the sum of all numbers in the array-x.

Time O(n)

Space O(n)

Java

# Algorithm - sliding window

In fact, we can also think in reverse. That is: our remaining array must be the middle part of the original array.

Does that mean that we only need to know the length of the sub-order sum equal to sum(nums)-x in the data. Just subtract it from the length of nums?

Since our goal is the smallest operand, we only require the sum to be the longest sub-sequence of a fixed value, which is a typical sliding window problem.

Java

Typical DFS.

# Code

Java

Java

class Solution {
public int minOperations(int[] nums, int x) {
int maxLength = -1;
int sum = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, -1);
int length = nums.length;
int[] prefixSums = new int[length];
for (int i = 0; i < length; i++) {
sum += nums[i];
prefixSums[i] = sum;
map.put(sum, i);
}
int remainSum = sum - x;
for (int i = 0; i < length; i++) {
int prefixSum = prefixSums[i];
if (map.containsKey(prefixSum - remainSum))
maxLength = Math.max(maxLength, i - map.get(prefixSum - remainSum));
}
if (maxLength == -1)
return -1;
else
return length - maxLength;
}
}