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

滑动窗口

方法一滑动窗口

这个题要求求最小的操作次数和可获得的最大点数类似，可以转化为求和为固定数的连续最长的子序列，本质是一个滑动窗口问题。
控制两个指针变量left，right。right负责窗口的扩张，left负责窗口的收缩。当窗口的合大于目标数的时候，窗口应该收缩。当窗口和小于目标数的时候，窗口应当扩张。

参考代码

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        target = sum(nums) - x
        left,right,total = 0,0,0
        ret = -1 
        while right < len(nums):
            total += nums[right]
            while total > target and left <= right:
                total -= nums[left]
                left += 1
            if total == target:
                ret = max(right - left + 1 , ret)
            right += 1    
        return -1 if ret == -1 else len(nums) - ret

复杂度分析

时间复杂度 O(n) 遍历了两遍数组
空间复杂度 O(1)