1658. Minimum Operations to Reduce X to Zero (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def minOperations(self, nums, x):
        """
        :type nums: List[int]
        :type x: int
        :rtype: int
        """
        # sliding window
        target = sum(nums) - x
        nums.append(0)
        n, result = len(nums), float("inf")
        cur = i = j = 0
        while i <= j and j < n:
            if cur == target:
                result = min(result, n - 1 - (j - i))
                cur += nums[j] - nums[i]
                i += 1
                j += 1
            elif cur < target:
                cur += nums[j]
                j += 1
            else:
                cur -= nums[i]
                i += 1
        return -1 if result == float("inf") else result
        
        # prefix sum
        nums = [0] + nums
        n = len(nums)
        for i in range(n - 1):
            nums[i + 1] += nums[i]
        target = nums[-1] - x
        result = float("inf")
        h = {0: -1}
        for i, num in enumerate(nums):
            if num - target in h:
                result = min(result, n - 1 - (i - h[num - target]))
            h[num] = i
        return -1 if result == float("inf") else result    
        
        # dfs TLE
        self.result = float("inf")
        def dfs(nums, x, count):
            if x == 0:
                self.result = min(self.result, count)
                return
            if nums and x > 0 and count < self.result:
                dfs(nums[1 : ], x - nums[0], count + 1)
                dfs(nums[ : len(nums) - 1], x - nums[-1], count + 1)
        dfs(nums, x, 0)
        return -1 if self.result == float("inf") else self.result