【滑动窗口】将 x 减到 0 的最小操作数

news/2024/9/15 23:17:36/ 标签: java, 开发语言

将 x 减到 0 的最小操作数

将 x 减到 0 的最小操作数
- 题目
- 思路讲解
- 代码书写

将 x 减到 0 的最小操作数

题目

题目链接: 将 x 减到 0 的最小操作数

思路讲解

按照题目的思路去做这一题是非常恶心的, 因此我们采用正难则反思路. 将问题转换为: 求中间某一个最长的数组长度, 使其和为sum - x, 其中 sum 是数组中所有数的总和

那么此时这个题目就被我们转换为了这一题的类似题目: 长度最小的子数组. 他这里是求长度最小的大于等于的, 我们这里就是求长度最大的只能等于的, 那么这一题是否也能用滑动窗口呢? 我们需要进行暴力优化看看

首先我们的暴力思路就是, 枚举所有子数组, 看看什么时候和为 target = sum - x, 并且找出长度最大值.

在这里插入图片描述

那此时有一个问题, 如果我的 target = 1, 此时遇到了下面的这个情况, 还有没有必要后走?

在这里插入图片描述

很明显没有必要了, 你这个时候区间里面的和都 > 1了, 你再往后加那就还更大, 怎么可能等于 target 呢? 当然这里依旧是由于本题有正整数的性质, 因此是可以这样优化的.

所以我们首先可以知道的是, right 是不一定要遍历完的, 当总和比 target 大后, 就可以直接停了.

接下来就是下一个问题, right 有没有必要回到 left 再次遍历呢? 我们依旧是看例子

在这里插入图片描述

当然也是没有必要的, 因为你要求区间里面的和至少要 target. 你刚刚区间, 就恰好是 >= target 的边界. 也就是说, 左边的值应该都是 <= target 的, 也就是下面这个图蓝色区间的和, 肯定是小于 target 的. 因为是正好加了右侧指针的值才 >= target 停下的

! 在这里插入图片描述

那你这个时候, 回去重新走一次, 这不是有病吗? 你肯定还是要走回到 4 这个位置的, 那你回去干什么呢? 因此我们可以推断出, left 和 right 是可以同向移动的, 那么就是经典的滑动窗口问题

因此我们还是老套路, 进行三步走

进窗口: 很明显, 我们需要将 right 指向的值放入到 sum 里进行维护
条件判断 + 出窗口: 出窗口, 主要就是 sum 太大了, 就需要出窗口, 出到 sum <= target 的时候就可以了.
更新结果: 结果的更新, 可以说是最好写的一个部分, 你要什么, 你就在什么时候更新. 我们要的是 sum = target 的长度, 那我们就在 sum = target 的时候更新长度不就行了?

当然, 更新结果的难点在于你把他放哪, 我们这里是在条件判断走完的时候, 才可能遇到 sum == target 的情况, 因此就在那里更新即可.

但是这个题看似简单, 实际上有非常多的细节问题, 还是非常恶心的, 我们依次来看

如果刚开始算出 target < 0, 那么此时我们要在一个正整数数组里面找小于 0 的区间, 肯定不可能, 直接返回. 如果不返回, 中间会因为 sum 恒大于 target 从而导致 left 一直出窗口, 最后越界

此时可能有人问了, target = 0 呢? 实际上这个是合理的, 我们找一个区间, 一个数字都不包含, 那不就是 0 了吗, 因此这个是合理的. 但此时又引出了一个细节问题
我们要找一个区间, 一个数字都不包含, 此时要求区间长度是 0, 那么我们能用 right - left + 1 这个算法来算长度吗? 很明显就不行了, 我们只能使用 right - left, 并且由于这个设定, 我们的更新结果, 必须放在 right++ 的后面.

如果不放在 right++ 的后面会导致一个什么问题?

假设数组里面只有一个 1, target = 0. 也就是我需要找一个长度为 0 的区间. 此时 left 会先到外面, 而 right 还指向着 1 这个数字

此时很明显是不合理的, 而此时我们就需要等 right 出来后, 移动一下, 随后我们就可以进行计算了.

假如使用的是 right - left + 1, 此时还正好就可以处理掉这种情况, 因为 + 1 相当于直接替代了 right 的一次 ++, 也不会出现问题.
中间的 length 我们可以赋值一个非法值, 例如 -1. 因为如果找不到等于 target 的区间, 那么最后我们需要返回 -1. 如果设定为 0 的话, 由于 0 是合法的, 我们不能确定这个 0 是不是正确的结果. 因此设定一个非法值方便我们判断.
我们求出的最大长度并不是答案, 而是我们通过思路转换后的目标值, 题目要求的是最小个数, 因此我们要用数组长度 - 目标值, 就可以得到最终答案了. 正难则反虽然好, 但是如果忘记了把结果也反过来, 那就白搭.

代码书写

java">class Solution {public int minOperations(int[] nums, int x) {// 先求 targetint n = nums.length, numSum = 0;for(int i = 0; i < n; i++) numSum += nums[i];int target = numSum - x;System.out.println(target);if(target < 0) return -1;// 滑动窗口int sum = 0, length = -1, left = 0, right = 0;while(right < n){// 进窗口sum += nums[right];// 条件判断 + 出窗口while(sum > target){sum -= nums[left++];}right++;// 更新结果if(sum == target) length = Math.max(length, right - left);}// 返回结果记得取反, 同时注意细节问题return length == -1 ? length : n - length;}
}

如果有人的思路是在出窗口的时候更新结果, 那么大概率代码如下

java">while(right < n){// 进窗口sum += nums[right];// 条件判断 + 出窗口while(sum >= target){// 更新结果if(sum == target) length = Math.max(length, right - left + 1);sum -= nums[left++];}right++;
}