Minimum Operations to Reduce X to Zero (M)
题目
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 <= 10^5
1 <= nums[i] <= 10^4
1 <= x <= 10^9
题意
给定一个数组,从头部或尾部取出连续的若干数,使其和为指定值,求这样的若干数的最小数量。
思路
求头部或尾部连续的最少的数,可以转化为求数组中一个最长的子数组,使其和正好为数组之和减去指定值。而求这样的最长子数组可以用滑动窗口来解决。
代码实现
Java
class Solution {
public int minOperations(int[] nums, int x) {
int target = -x;
for (int num : nums) {
target += num;
}
if (target <= 0) return target == 0 ? nums.length : -1;
int sum = 0, maxLen = -1;
int left = 0, right = 0;
while (left < nums.length) {
if (sum < target) {
if (right == nums.length) break;
sum += nums[right++];
} else if (sum > target) {
sum -= nums[left++];
} else {
maxLen = Math.max(maxLen, right - left);
if (right == nums.length) break;
sum += nums[right++];
sum -= nums[left++];
}
}
return maxLen == -1 ? -1 : nums.length - maxLen;
}
}