1695. 删除子数组的最大得分

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums。你需要从数组中删除一个含有若干不同元素的子数组（即子数组中不能有重复元素）。
删除子数组的得分是该子数组所有元素的和。
请你返回可以获得的最大得分。

说明：

  • 这是一个不定长滑动窗口问题。

  • 核心逻辑是维护一个“所有元素互不相同”的窗口。

  • 当遇到重复元素时，收缩左边界，直到窗口内再次满足无重复条件。

  • 与“无重复字符的最长子串”不同的是，这里优化的目标是元素和最大，而不是长度最长。

  • 示例：

  • 示例 1：

1
2
3
4
5
输入：nums = [4,2,4,5,6]
输出：17
解释：
最优子数组是 [2,4,5,6]，和为 17。
（注意：不能包含第一个 4，因为后面还有一个 4）
  • 示例 2：
1
2
3
4
输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：
最优子数组是 [5,2,1] 或 [1,2,5]，和为 8。

💻 解题思路

思路1：不定长滑动窗口

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        count = Counter()   # 哈希表，记录窗口内每个数字出现的次数
        ans = 0             # 记录当前窗口内元素的和（当前得分）
        result = 0          # 记录历史最大得分
        left = 0            # 窗口左边界
        
        # 右边界 right 随循环遍历数组
        for right, num in enumerate(nums):
            # 1. 扩展窗口：将当前数字加入哈希表和当前和
            count[num] += 1
            ans += num
            
            # 2. 收缩窗口：如果当前数字出现次数超过 1（即出现重复）
            # 则不断移动左边界，直到当前数字次数恢复为 1
            while count[num] > 1:
                count[nums[left]] -= 1
                ans -= nums[left]  # 移除左边元素时，从当前和中减去
                left += 1
            
            # 3. 更新结果：此时窗口 [left, right] 内无重复元素
            # 更新最大得分
            result = max(ans, result)
            
        return result

思路1：📊 性能分析

  • 时间复杂度：O(N)O(N)
    • 其中 NN 是数组 nums 的长度。
    • 虽然代码中有一个 while 循环嵌套在 for 循环中，但每个元素最多被访问两次（一次被右边界 right 加入，一次被左边界 left 移出）。因此，整体操作次数是线性的。
  • 空间复杂度：O(N)O(N)
    • 哈希表 count 在最坏情况下（数组所有元素都不同）需要存储 NN 个键值对。

思考

  1. 与“最长无重复子串”的对比：

    • 相同点：都使用滑动窗口维护“无重复元素”的条件，收缩逻辑完全一致（while count[num] > 1）。
    • 不同点：
      • 最长子串问题更新的是 max(len)。
      • 本题更新的是 max(sum)。
    • 因此，代码中多维护了一个变量 ans 来实时计算窗口内的元素和。

  2. 和的维护：

    • 在扩展窗口时：ans += num。
    • 在收缩窗口时：ans -= nums[left]。
    • 这保证了 ans 始终等于当前窗口 [left, right] 内所有元素的和。

  3. 结果更新：

    • result = max(ans, result) 放在 while 循环之后。
    • 确保只有在窗口合法（无重复元素）时，才尝试更新最大得分。