文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書
1. Description
Minimum Operations to Reduce X to Zero
2. Solution
解析：Version 1，這道題跟Leetcode 560的解法很像瘤旨，首先計算數(shù)組的總和total，如果total < x，則無論如何也不會將x減到0钻蹬，如果total = x客扎，則需要移除所有元素才能將x變?yōu)?code>0岳枷，由于x一直是從最左或最右移除，因此問題可以變?yōu)椋赫业揭粋€最大連續(xù)子數(shù)組卧蜓，使得其和為total - x，這樣可以保證剩下的元素之和等于x把敞，個數(shù)最少弥奸，剩下元素位于左右子數(shù)組的左右兩側(cè)。使用前綴和方法奋早，依次求數(shù)組的前綴和盛霎，并將前綴和以及當(dāng)前索引位置記錄到字典stat中赠橙，要尋找的連續(xù)子數(shù)組和為target，如果當(dāng)前前綴和減去target位于字典中愤炸，則計算子數(shù)組的長度并更新最大子數(shù)組長度maximum期揪，注意如果當(dāng)前前綴和剛好等于target，此時尋找的差為0规个，為了保證正確的子數(shù)組長度凤薛，stat[0] = -1，最后诞仓，如果maximum的值一直沒更新缤苫，則說明沒找滿足條件的子數(shù)組葫慎，此時應(yīng)返回-1担巩，否則，返回n - maximum酝陈。Version 2移除了數(shù)組和與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
