将 x 减到 0 的最小操作数
难度:
标签:
题目描述
代码结果
运行时间: 85 ms, 内存: 27.0 MB
/*
* Java Stream Solution:
* This problem doesn't particularly lend itself to a pure Stream-based solution
* because it involves finding subarrays, which are more naturally handled with loops.
* However, we can still utilize streams for array processing such as calculating sums.
*/
import java.util.Arrays;
public class Solution {
public int minOperations(int[] nums, int x) {
int totalSum = Arrays.stream(nums).sum();
int target = totalSum - x;
if (target < 0) return -1;
if (target == 0) return nums.length;
int n = nums.length;
int maxLength = -1, currentSum = 0;
int left = 0;
for (int right = 0; right < n; right++) {
currentSum += nums[right];
while (currentSum > target) {
currentSum -= nums[left];
left++;
}
if (currentSum == target) {
maxLength = Math.max(maxLength, right - left + 1);
}
}
return maxLength == -1 ? -1 : n - maxLength;
}
}
解释
方法:
题解采用的是转化问题的思路:将问题转化为在数组中找到一个连续子数组,其和为 sum(nums) - x,这样子数组外的元素之和就刚好等于 x。这可以通过滑动窗口技术来实现。首先,若求出的目标和 tar 小于0,则说明不可能实现,返回-1。如果 tar 等于0,则说明整个数组的和刚好等于 x,直接返回数组长度。接下来使用两个指针 left 和 right 来定义一个窗口,并在数组上滑动这个窗口,尝试找到和为 tar 的最长子数组。每次右指针 right 向右移动,将 nums[right] 加到窗口的累计和 cnt 中。如果 cnt 超过了 tar,就移动左指针 left 直到 cnt 不超过 tar。每找到一个符合条件的窗口,就尝试更新结果 res(最长符合条件子数组的长度)。最后,返回整个数组长度减去这个最长的子数组长度,得到的就是最小的操作次数。如果没有找到任何符合条件的子数组,则返回 -1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解法中提到如果目标和 tar 小于 0,则返回 -1。请问为什么 tar 小于 0 就一定不能通过移除元素来使 x 减到 0?
▷🦆
解法中的滑动窗口是寻找最长的和为 tar 的子数组。请问为什么必须找到最长的子数组,较短的符合条件的子数组是否也可以?
▷🦆
滑动窗口在处理 cnt 大于 tar 时,通过移动左指针来调整。能否详细解释为什么移动左指针可以帮助找到正确的子数组长度?
▷🦆
在题解中,当 tar 等于 0 时,直接返回数组的长度。这种情况下是否意味着整个数组的和就等于 x?如果是,为什么这样就能确定是最小操作数?
▷