将 x 减到 0 的最小操作数
1658. 将 x 减到 0 的最小操作数
给你一个整数数组 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 <= 10^51 <= nums[i] <= 10^41 <= x <= 10^9
相关题 LC2516 和LC1423
逆向思维，取补，滑动窗口
把问题转换成「从 nums中移除一个最长的子数组，使得剩余元素的和为 x」。把离散变成连续。
正数保证了窗口和的单调性，所以可以用滑动窗口。如果存在负数的话就没有这个性质了，也就不能确定什么时候扩大和缩小窗口， 也就不能使用滑动窗口算法，而应该使用前缀和 + 哈希表的方式 解决， 参见 560. 和为K的子数组。如果窗口和等于sum-target，则找到了一个可行解。
class Solution {
public int minOperations(int[] nums, int x) {
int n = nums.length, sum = 0;
// 计算总和
for (int i = 0; i < n; i++) {
sum += nums[i];
}
// 滑动窗口需要寻找的子数组目标和
int target = sum - x;
// 滑动窗口左右边界
int left = 0, right = 0;
// 记录窗口内所有元素和
int windowSum = 0;
// 记录目标子数组的最大长度
int maxLen = Integer.MIN_VALUE;
// 开始执行滑动窗口框架
while (right < nums.length) {
// 扩大窗口
windowSum += nums[right];
right++;
while (windowSum > target && left < right) {
// 缩小窗口
windowSum -= nums[left];
left++;
}
// 寻找目标子数组。缩小完窗口后windowSum会小于等于target。
if (windowSum == target) {
maxLen = Math.max(maxLen, right - left);
}
}
// 目标子数组的最大长度可以推导出需要删除的字符数量
return maxLen == Integer.MIN_VALUE ? -1 : n - maxLen;
}
}- 时间复杂度：O(n)，其中 n 为 nums 的长度。left 和 right 均最多遍历整个数组一次。
- 空间复杂度：O(1)，仅用到若干额外变量。
为什么不能这样写？
while (windowSum >= target && left < right) {
// 寻找目标子数组
if (windowSum == target) {
maxLen = Math.max(maxLen, right - left);
break;
}
// 缩小窗口
windowSum -= nums[left];
left++;
}因为当left=right时会退出while循环，但是可能target=0，所以此时windowSum==target还是满足的，应该计算一下最大长度。
首先要去掉 left < right或者把它改为left<=right，然后要在滑动窗口前加一个判断target是否为负的判断。加这两个条件是因为target可能为0或负数。
class Solution {
public int minOperations(int[] nums, int x) {
int n = nums.length, sum = 0;
// 计算总和
for (int i = 0; i < n; i++) {
sum += nums[i];
}
// 滑动窗口需要寻找的子数组目标和
int target = sum - x;
if (target < 0) return -1;
// 滑动窗口左右边界
int left = 0, right = 0;
// 记录窗口内所有元素和
int windowSum = 0;
// 记录目标子数组的最大长度
int maxLen = Integer.MIN_VALUE;
// 开始执行滑动窗口框架
while (right < nums.length) {
// 扩大窗口
windowSum += nums[right];
right++;
while (windowSum >= target && left <= right) {
// 寻找目标子数组
if (windowSum == target) {
maxLen = Math.max(maxLen, right - left);
break;
}
// 缩小窗口
// 如果 x 比 数组的和还要大，那么left和right就会走到数组的末尾，然后又进不去上面的if，所以会来到这里，然后出现越界
// 所以要在上面判断一下target是否为负
windowSum -= nums[left];
left++;
}
}
// 目标子数组的最大长度可以推导出需要删除的字符数量
return maxLen == Integer.MIN_VALUE ? -1 : n - maxLen;
}
}前缀和+二分查找
因为数组中都是正数，所以前缀和是递增的，所以可以用二分查找。
import java.util.Arrays;
class Solution {
public int minOperations(int[] nums, int x) {
int n = nums.length;
int sum = Arrays.stream(nums).sum();
int target = sum - x;
if (target < 0) return -1;
if (target == 0) return n;
// 计算前缀和数组
int[] prefixSums = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
int maxLength = -1;
// 使用二分查找寻找最长的子数组
for (int i = 0; i <= n; i++) {
int toFind = prefixSums[i] - target;
// [0,i)中前缀和为toFind的位置，因为窗口中没有零，全是正数，所以该位置只有一个。
int index = Arrays.binarySearch(prefixSums, 0, i, toFind);
if (index >= 0) { // 非负说明存在该数，负数说明前缀和数组中不存在toFind这个数。注意和为toFind的区间是[index+1, i]。
maxLength = Math.max(maxLength, i - index);
}
}
return maxLength == -1 ? -1 : n - maxLength;
}
}时间复杂度为 O(n + n log n)，即 O(n log n)。空间复杂度为 O(n)。
Arrays.binarySearch的返回值的意义
- 找到目标元素时：
- 如果在数组中找到了目标元素，
Arrays.binarySearch返回目标元素在数组中的索引。 - 例如，如果数组
arr是[1, 3, 5, 7, 9]，执行Arrays.binarySearch(arr, 5)将返回索引2，因为5在数组中的索引是2。
- 如果在数组中找到了目标元素，
- 未找到目标元素时：
- 如果数组中不存在目标元素，
Arrays.binarySearch会返回一个负数，这个负数可以用来推断出目标元素如果插入时应该插入的位置。 - 具体来说，它返回值为
-insertionPoint - 1，其中insertionPoint是目标元素应该插入的位置索引，使得数组保持有序。 - 例如，如果数组
arr是[1, 3, 5, 7, 9]，执行Arrays.binarySearch(arr, 4)将返回-3，因为4不在数组中，但应插入在索引2的位置（即5前面），那么-insertionPoint - 1 = -2 - 1 = -3。
- 如果数组中不存在目标元素，
前缀和+哈希表，构造映射
构造前缀和到索引的映射。没有用到前缀和的有序性，而是直接用哈希表实现了 O(1) 的查询。
每计算一个新的前缀和p[i]，都要把它加入哈希表，然后去哈希表中检查是否已经存在一个前缀和p[j]满足p[i]-p[j]=arrSum-x，即中间的数组和是arrSum-x，这样两边的数组和就是x。
class Solution {
public int minOperations(int[] nums, int x) {
// 先将 x 变成负数，因为我们会通过加上数组中的元素使 x 减少到 0
x = -x;
// 计算整个数组的和，并将其加到 x 上，即计算arrSum-x
for (int v : nums) {
x += v;
}
// 用于存储前缀和及其对应的索引。重点。
Map<Integer, Integer> vis = new HashMap<>();
// 初始化，前缀和为 0 的时候，索引为 -1。重点。
vis.put(0, -1);
int n = nums.length;
// 初始化答案为一个很大的数，用来存储最小操作数
int ans = 1 << 30;
// 遍历数组，计算前缀和，s代表前缀和
for (int i = 0, s = 0; i < n; ++i) {
s += nums[i];
// 记录前缀和及其对应的索引
vis.putIfAbsent(s, i);
// 检查是否存在一个前缀和，使得当前前缀和减去 x 后的值存在于 vis 中
if (vis.containsKey(s - x)) {
int j = vis.get(s - x); // 获取该前缀和对应的索引
// 计算操作数，并更新最小操作数
ans = Math.min(ans, n - (i - j));
}
}
// 如果 ans 没有更新，返回 -1；否则返回最小操作数
return ans == 1 << 30 ? -1 : ans;
}
}时间复杂度：O(n)，其中 n 为 nums 的长度。
空间复杂度：O(n)。