LeetCode 1695. Maximum Erasure Value 疑问

[JasonLaw]

我正在解决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]

sum 需要用一个变量存储，r+1 时加 nums[r]，l+1 时减 nums[l]

[JasonLaw]

@chitaotao #1 我知道使用这个不会出现 Time Limit Exceeded ，是 sum(window)有问题？ r + 1 时加 nums[r]应该跟 sum(window)是等价才对的。🤕

[chitaotao]

@JasonLaw sum(window) 每次调用都要从头把集合加起来

[JasonLaw]

@chitaotao #3 从头指的是从 index 0 开始？

[JasonLaw]

@chitaotao #3 我傻了😅 因为 sum(window)每次都会从 l 开始，会有很多不必要的工作，但是维护多一个 window_sum 就不会。