Manjusaka

09-20 leetcode 1658

链接 1658. Minimum Operations to Reduce X to Zero

题目

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.

题解

解法1 是滑动窗口暴力求解

class Solution:
    def minOperations(self, nums: list[int], x: int) -> int:
        target, size, window_sum, low, n = sum(nums) - x, -1, 0, -1, len(nums)
        for high, num in enumerate(nums):
            window_sum += num
            while low + 1 < n and window_sum > target:
                low += 1
                window_sum -= nums[low]
            if window_sum == target:
                size = max(size, high - low)
        return -1 if size < 0 else n - size

解法2 是前缀和+hashmap 做索引

class Solution:
    def minOperations(self, nums: list[int], x: int) -> int:
        length, total, prefix_sum, results = len(nums), sum(nums), 0, -1
        target, sum_index = total - x, {0: -1, total: length - 1}
        for index, value in enumerate(nums):
            prefix_sum += value
            if prefix_sum - target in sum_index:
                results = max(results, index - sum_index[prefix_sum - target])
            sum_index[prefix_sum] = index
        return -1 if results < 0 else length - results