V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
JasonLaw
V2EX  ›  程序员

LeetCode 1695. Maximum Erasure Value 疑问

  •  
  •   JasonLaw · 2023-01-31 23:14:01 +08:00 · 768 次点击
    这是一个创建于 647 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我正在解决Maximum Erasure Value - LeetCode,我的 solution 如下,但是出现了 Time Limit Exceeded ,我不太明白为什么,时间复杂度明明是 O(n)呀。🤐

    class Solution:
        def maximumUniqueSubarray(self, nums: List[int]) -> int:
            # sliding window solution
            res = 0
            window, l, r = set(), 0, 0
            while r < len(nums):
                while r < len(nums) and nums[r] not in window:
                    window.add(nums[r])
                    r += 1
                res = max(res, sum(window))
                if r == len(nums):
                    return res
                while nums[r] in window:
                    window.remove(nums[l])
                    l += 1
            return res
    

    不知道为什么 test case 的 nums 是空的。🤐

    chitaotao
        1
    chitaotao  
       2023-02-01 00:07:52 +08:00 via Android
    sum 需要用一个变量存储,r+1 时加 nums[r],l+1 时减 nums[l]
    JasonLaw
        2
    JasonLaw  
    OP
       2023-02-01 07:48:39 +08:00 via iPhone
    @chitaotao #1 我知道使用这个不会出现 Time Limit Exceeded ,是 sum(window)有问题? r + 1 时加 nums[r]应该跟 sum(window)是等价才对的。🤕
    chitaotao
        3
    chitaotao  
       2023-02-01 07:55:38 +08:00 via Android
    @JasonLaw sum(window) 每次调用都要从头把集合加起来
    JasonLaw
        4
    JasonLaw  
    OP
       2023-02-01 08:27:14 +08:00
    @chitaotao #3 从头指的是从 index 0 开始?
    JasonLaw
        5
    JasonLaw  
    OP
       2023-02-01 09:45:11 +08:00
    @chitaotao #3 我傻了😅 因为 sum(window)每次都会从 l 开始,会有很多不必要的工作,但是维护多一个 window_sum 就不会。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1099 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 18:59 · PVG 02:59 · LAX 10:59 · JFK 13:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.