Leetcode 1658. Minimum Operations to Reduce X to Zero

柔光的暖阳◎ 2022-09-09 00:10 15阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 1. Description ##

![Minimum Operations to Reduce X to Zero][]

## 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 -1
            if total == x:
                return n
            target = total - x
            prefix = 0
            stat = {
        }
            stat[0] = -1
            maximum = -1
            for i in range(n):
                prefix += nums[i]
                stat[prefix] = i
                if prefix - target in stat:
                    maximum = max(maximum, i - stat[prefix - target])
            if maximum == -1:
                return -1
            return n - maximum

*  Version 2

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

## Reference ##

1.  [https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/][https_leetcode.com_problems_minimum-operations-to-reduce-x-to-zero]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Minimum Operations to Reduce X to Zero]: /images/20220829/2f3883d2d2e34b08aeaf682626d4df11.png
[https_leetcode.com_problems_minimum-operations-to-reduce-x-to-zero]: https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/