1658. 将x减到0的最小操作数Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1
示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 104
- 1 <= x <= 109
# 思路
滑动窗口找中间最长的片段使得sum(片段)=sum(nums)-x
# 解法
class Solution {
public int minOperations(int[] nums, int x) {
int maxPart = -1;
int sum = Arrays.stream(nums).sum();
int currentSum = 0;
int left = 0;
int right = 0;
while (right < nums.length) {
if (right < nums.length) {
currentSum += nums[right++];
}
while (currentSum > sum - x && left < nums.length) {
currentSum -= nums[left++];
}
if (currentSum == sum - x) {
maxPart = Math.max(maxPart, right - left);
}
}
return maxPart == -1 ? -1 : nums.length - maxPart;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 总结
- 分析出几种情况，然后分别对各个情况实现
