leetcode
leetcode 1501 ~ 1550
将 x 减到 0 的最小操作数

将 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 是通过计算 sum(nums) - x 得到的,它代表了我们需要在数组中找到的子数组的和。如果 tar 小于0,意味着 x 大于整个数组的和,这说明你无法通过移除数组中的任何元素组合来得到 x,因为即使移除所有元素,得到的和也只是整个数组的和,而这个和小于 x。因此,当 tar 小于 0 时,不可能通过移除元素达到目标 x,所以返回 -1。
🦆
解法中的滑动窗口是寻找最长的和为 tar 的子数组。请问为什么必须找到最长的子数组,较短的符合条件的子数组是否也可以?
在这个问题中,我们的目标是通过移除元素使数组的和减少到 x。因此,我们需要找到一个和为 tar = sum(nums) - x 的子数组,以使得剩余部分的和正好为 x。找到最长的和为 tar 的子数组意味着剩余部分的总和(即移除的部分)是最小的,从而使得我们移除的元素数量也是最小的。如果找到的是一个较短的和为 tar 的子数组,剩余部分的和仍为 x,但未被包含在子数组中的元素数量会更多,这并不符合我们减少操作次数的目标。
🦆
滑动窗口在处理 cnt 大于 tar 时,通过移动左指针来调整。能否详细解释为什么移动左指针可以帮助找到正确的子数组长度?
在使用滑动窗口策略时,当窗口内的元素总和(cnt)超过目标和(tar)时,表明窗口内包含了过多的元素,使得总和超标。此时,通过向右移动左指针(即缩小窗口的左边界),可以逐渐减少窗口内的元素总和。这个操作有助于调整窗口的大小,直到窗口内元素的总和再次等于或小于目标和 tar。这是一个试错的过程,通过不断调整(扩大或缩小)窗口,我们可以找到一个正好使得总和等于 tar 的子数组,从而确定最长的符合条件的子数组长度。
🦆
在题解中,当 tar 等于 0 时,直接返回数组的长度。这种情况下是否意味着整个数组的和就等于 x?如果是,为什么这样就能确定是最小操作数?
当 tar 等于 0 时,这意味着 x 等于整个数组的和(sum(nums))。因此,为了使数组的和减少到 x,我们需要移除的元素总和为 0,这实际上意味着我们不需要移除任何元素。然而,题目要求是通过移除元素使和减少到 x,所以在这种情况下,我们应该移除整个数组,使最终数组为空,从而达到将数组和减少到 x 的目标。因此,返回整个数组的长度,即移除所有元素的操作次数,是最小的操作数。

相关问题