前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 1658. Minimum Operations to Reduce X to Zero

Leetcode 1658. Minimum Operations to Reduce X to Zero

作者头像
Tyan
发布2021-09-06 15:26:45
4460
发布2021-09-06 15:26:45
举报
文章被收录于专栏:SnailTyan

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

1. Description

Minimum Operations to Reduce X to Zero
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
代码语言:javascript
复制
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
代码语言:javascript
复制
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/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/08/27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. Description
  • 2. Solution
  • Reference
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档