1658. 将 x 减到 0 的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数

题目描述

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。

如果可以将 x 恰好减到 0 ，返回最小操作数；否则，返回 -1 。

核心思考：正难则反与滑动窗口

这道题如果直接从两端向内进行搜索（如 DFS 递归），会因为分支过深和状态重叠带来较高的复杂度。针对这类“按一定规则剥离两侧端点”的问题，最优策略往往是正难则反（逆向思维）。

剥离左右两侧的节点使其和刚好为 x，并且要求两端剥离的节点数量最少（即最小操作数）。这一命题在数学和逻辑上，完全等价于在原数组中寻找到一个连续的“最长子数组”，使得该子数组内的元素和精确等于 sum(nums) - x。

完成命题转换后，该问题即从复杂的“两端双向剥离”退化为了经典的**单向滑动窗口（Sliding Window）**模型：

1. 计算目标和：令 target = sum(nums) - x。若 target < 0，则表明即使全部剔除也无法满足要求，直接判定无解，返回 -1。
2. 构建窗口：维护一个由左右指针 left 与 right 动态约束的弹性区间。
3. 右指针主导膨胀：right 持续向右推进，并将扫入的新元素纳入窗口累加状态量 windows_sum 中。
4. 左指针被动收缩：当窗口内部元素的累加状态溢出安全阈值（windows_sum > target）时，启动左端点淘汰出局逻辑（left 步进同时扣除对应元素权值），以此将区间和强行压退回临界要求以内。
5. 极值更新：每当 windows_sum == target 命中条件反射时，比对并刷新当下的窗口长度极限值 ans = max(ans, right - left)。

当两指针走完整个线性序列，最终的结果即为数组总长度扣除这个寻得的最长子数组跨度：l - ans。

解题思路 (Python)

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # 这道题等价于让你寻找 nums 中元素和为 sum(nums) - x 的最长子数组。
        target = sum(nums) - x
        if target < 0:
            return -1
        l = len(nums)
        left = right = 0
        windows_sum = 0
        # 初始化answer = -inf
        ans = float('-inf')
        while right < l:
            windows_sum += nums[right]
            right += 1
            while windows_sum > target and left < right:
                # 开始弹出左边的
                windows_sum -= nums[left]
                left += 1
            if windows_sum == target:
                ans = max(ans,right - left)
        
        if ans != float('-inf'):
            return l-ans
        else:
            return -1

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为数组 nums 的容纳长度。在整体滑动窗口运行的宏观周期里，right 指针与 left 指针分别且最多完成整个数组的一趟顺序寻址，不涉及回溯干涉，时间性能严格落定在线性量级。
• 空间复杂度：$O(1)$。算法逻辑底座未引入任何高开销的外部映射表或辅助结构池，只创建了少量的常数级游标控制指针与临时累加记录元，将内存消耗压减到最低。