1658. 将 x 减到 0 的最小操作数（Rating 1817）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1817

思路

本题等价于找到首尾连续的一段最短的“子数组”，其和等于x

可以基于首尾的滑动窗口解决，但是写起来有些麻烦。

考虑一种等价转换

找到数组nums中的最长子数组，使得该子数组的和为sum(nums) - x

同样也可以使用滑动窗口解决，这样就等价于找到了答案。

代码

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        t = sum(nums) - x # 目标数
        if t < 0: return -1 # 无解
        l, s = 0, 0 # 滑动窗口的左端点及和
        ret = -inf # 最长子数组的长度
        for r, num in enumerate(nums):
            s += num # 右端点向右滑动
            while s > t: # 左端点向右滑动满足要求
                s -= nums[l]
                l += 1
            if s == t: # 找到一个子数组满足
                ret = max(ret, r - l + 1)
        return len(nums) - ret if ret > -inf else -1