LC1658. 将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^(5) 1 <= nums[i] <= 10^(4) 1 <= x <= 10^(9)

题目解析

好的，没问题！我是 AlgoMooc 的算法老师，咱们今天就来搞定这道题。别怕，跟着我一步步走，你会发现它其实很简单。

---

### 题目在说什么

我们先来用大白话理解一下题目在干嘛。

想象一下，你面前有一排数字卡片（数组 nums），每张卡片上写着一个数字。现在，你手里有一个数字 x。

你的任务就是：从这排卡片的最左边或者最右边，一张一张地拿走卡片。每拿走一张，就把你手里的 x 减去卡片上的数字。

你的目标是：通过若干次这样的操作，让你手里的 `x` 正好变成 0。并且，我们希望用的操作次数（也就是拿走的卡片张数）尽可能少。

如果无论如何都没法让 x 变成 0，就返回 -1。

举个例子： 卡片是 [1, 1, 4, 2, 3]，x = 5。

• 你可以从右边拿走 3，x 变成 5 - 3 = 2。
• 再从右边拿走 2，x 变成 2 - 2 = 0。

这样，你只用了 2 次操作，就完成了任务。所以答案是 2。

你可能会想，从左边拿 1 和 4 也行啊？1 + 4 = 5，也是 2 次操作。没错，这也是一种解法。题目只要求返回最少的操作次数，所以 2 就是正确答案。

---

### 思路是怎么来的

这个题目的难点在于，我们只能从“两头”拿，不能从中间拿。这让我们感觉有点束手束脚。

换个角度想问题：

如果我们把整个数组的所有数字加起来，得到一个总和 totalSum。那么，我们拿走的那些数字之和，就是 x。而剩下的、没有被拿走的数字之和，就是 totalSum - x。

关键来了： 我们拿走的数字，都是从“两头”拿的。这意味着，剩下的那些数字，在原来的数组里，一定是连续的一整段（因为只能从两边拿，中间的部分是不会被拆散的）。

所以，问题就神奇地转化成了：

> 在数组里，找出一段最长的连续子数组，使得这个子数组里所有数字的和，恰好等于 `totalSum - x`。

为什么是“最长”的呢？因为我们要让“操作次数最少”。操作次数 = 拿走的卡片数 = 总卡片数 - 剩下的卡片数。剩下的卡片数（也就是我们找到的那个连续子数组）越长，操作次数就越少。

生活化比喻： 想象你有一排积木，你只能从最左边或最右边拆掉一些积木。你想拆掉一定数量的积木（总和为 x）。那么，剩下的积木，在中间一定是“连在一起”的一整段。我们要找的，就是这段“连在一起”的积木最长能有多长。剩下的积木越长，说明你拆掉的积木越少，操作次数也就越少。

总结一下思路： 1. 计算 targetSum = totalSum - x。 2. 在数组里找一个和等于 `targetSum` 的最长连续子数组。 3. 答案 = 数组长度 - 最长子数组长度。

如果 targetSum 本身是 0，说明我们需要拿走所有卡片，操作次数就是数组长度。 如果找不到这样的子数组，说明无解，返回 -1。

---

### 代码逐步拆解

现在，我们来看看参考代码是怎么实现这个思路的。它用了一个非常经典的技巧：滑动窗口。

想象你有一个可以伸缩的“窗口”，这个窗口盖住数组里的一段连续数字。我们通过移动窗口的左右边界，来寻找和为 targetSum 的最长窗口。

class Solution {
    public int minOperations(int[] nums, int x) {
        // 1. 计算总和和目标值
        int targetSum = 0;
        for (int num : nums) {
            targetSum += num;
        }
        targetSum -= x; // 现在 targetSum 就是我们要找的连续子数组的和
        
        // 特殊情况：如果目标值就是0，说明要移除所有元素
        if (targetSum == 0) {
            return nums.length;
        }

        // 2. 初始化滑动窗口
        int windowSum = 0;      // 当前窗口内数字的和
        int windowLenMax = 0;   // 记录找到的符合条件的最长窗口长度
        int left = 0;           // 窗口的左边界

        // 3. 右指针 right 从0开始，遍历整个数组
        for (int right = 0; right < nums.length; right++) {
            // A1: 把右边的新元素加入窗口
            windowSum += nums[right];

            // A2: 如果窗口的和太大了，就从左边缩小窗口
            //     直到窗口和 <= targetSum
            while (left <= right && windowSum > targetSum) {
                windowSum -= nums[left];
                left++;
            }

            // A3: 检查一下，现在的窗口和是不是正好等于 targetSum
            //     如果是，就更新一下最大窗口长度
            if (windowSum == targetSum) {
                windowLenMax = Math.max(windowLenMax, right - left + 1);
            }
        }

        // 4. 根据结果返回答案
        //    如果从来没找到过符合条件的窗口，windowLenMax 就是0，返回-1
        //    否则，操作数 = 总长度 - 最长窗口长度