Leetcode 1658. Minimum Operations to Reduce X to Zero

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**Version 1，这道题跟Leetcode 560的解法很像，首先计算数组的总和total，如果total < x，则无论如何也不会将x减到0，如果total = x，则需要移除所有元素才能将x变为0，由于x一直是从最左或最右移除，因此问题可以变为：找到一个最大连续子数组，使得其和为total - x，这样可以保证剩下的元素之和等于x，个数最少，剩下元素位于左右子数组的左右两侧。使用前缀和方法，依次求数组的前缀和，并将前缀和以及当前索引位置记录到字典stat中，要寻找的连续子数组和为target，如果当前前缀和减去target位于字典中，则计算子数组的长度并更新最大子数组长度maximum，注意如果当前前缀和刚好等于target，此时寻找的差为0，为了保证正确的子数组长度，stat[0] = -1，最后，如果maximum的值一直没更新，则说明没找满足条件的子数组，此时应返回-1，否则，返回n - maximum。Version 2移除了数组和与x的比较，效率要差一些。

• Version 1

class Solution:def minOperations(self, nums: List[int], x: int) -> int:n = len(nums)total = sum(nums)if total < x:return -1if total == x:return ntarget = total - xprefix = 0stat = {
    }stat[0] = -1maximum = -1for i in range(n):prefix += nums[i]stat[prefix] = iif prefix - target in stat:maximum = max(maximum, i - stat[prefix - target])if maximum == -1:return -1return n - maximum

• Version 2

class Solution:def minOperations(self, nums: List[int], x: int) -> int:n = len(nums)target = sum(nums) - xprefix = 0stat = {
    }stat[0] = -1maximum = -1for i in range(n):prefix += nums[i]stat[prefix] = iif prefix - target in stat:maximum = max(maximum, i - stat[prefix - target])if maximum == -1:return -1return n - maximum

Reference

1. https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/