2841. 几乎唯一子数组的最大和#

题目描述#

给你一个整数数组 nums 和两个正整数 m 和 k。

返回 nums 中长度为 k 且包含至少 m 个不同元素的子数组的最大和。如果不存在这样的子数组，返回 0。

示例 1：

1
输入：nums = [2,6,7,3,1,7], m = 3, k = 4
2
输出：18
3
解释：有 3 个长度为 4 的子数组：[2,6,7,3] 和 18，[6,7,3,1] 和 17，[7,3,1,7] 和 18。
4
其中 [2,6,7,3] 和 [7,3,1,7] 都包含 3 个不同元素，最大和为 18。

示例 2：

1
输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
2
输出：23

提示：

1 <= m <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^9

解法思路#

定长滑动窗口 + 哈希表维护窗口内元素的频次（本题难点在于要在 O(1) 内知道窗口里有多少个互不相同的元素）。

如何 O(1) 维护「不同元素个数」：用一个 Counter（频次哈希表）记录窗口内每个元素的出现次数。那么 len(window) 就是窗口内互不相同元素的个数。窗口滑动时：

右端点进窗口：window[nums[i]] += 1；
左端点出窗口：对应的频次减一；一旦频次减到 0 就 del window[out]，这样哈希表的键数（即不同元素个数）始终准确。

沿用 入-更新-出 三步，窗口和为 cur：

入：右端点 nums[i] 进窗口并更新频次与 cur；窗口不足 k 时继续。
更新：窗口长度为 k 时，若 len(window) >= m（是「几乎唯一」子数组），用 cur 更新最大和 ans。
出：左端点 nums[i-k+1] 出窗口，频次减一（减到 0 则删除键），并从 cur 中扣除。

初值：第一个窗口若无 m 个不同元素，ans 保持 0（没有满足条件的子数组返回 0）。

逐步举例（nums = [2,6,7,3,1,7], m = 3, k = 4）。枚举所有长 4 窗口并检查不同元素数：

窗口	不同元素	是否 ≥3	和
[2,6,7,3]	4	✅	18 → `ans=18`
[6,7,3,1]	4	✅	17
[7,3,1,7]	3	✅	18 → `ans=18`

三种都是”几乎唯一”子数组，最大和 ans = 18，与预期一致。

思路与写法参考灵茶山艾府 2841、2461 对应题解（2461 是在本题基础上的特例：把 >= m 换成 == k）。

复杂度分析#

时间复杂度：O(n)，每个元素进出窗口各一次。
空间复杂度：O(k)，哈希表大小不超过窗口长度。

代码实现#

1
from collections import Counter
2

3

4
class Solution:
5
    def maxSum(self, nums: list[int], m: int, k: int) -> int:
6
        window = Counter(nums[:k])
7
        cur = sum(nums[:k])
8
        ans = cur if len(window) >= m else 0
9
        for i in range(k, len(nums)):
10
            out = nums[i - k]
11
            window[out] -= 1
12
            if window[out] == 0:
13
                del window[out]
14
            window[nums[i]] += 1
15
            cur += nums[i] - out
16
            if len(window) >= m and cur > ans:
17
                ans = cur
18
        return ans

1
import unittest
2

3

4
class TestMaxSum(unittest.TestCase):
5
    def setUp(self):
6
        self.solution = Solution()
7

8
    def test_example1(self):
9
        self.assertEqual(self.solution.maxSum([2, 6, 7, 3, 1, 7], 3, 4), 18)
10

11
    def test_example2(self):
12
        self.assertEqual(self.solution.maxSum([5, 9, 9, 2, 4, 5, 4], 1, 3), 23)
13

14
    def test_no_subarray(self):
15
        self.assertEqual(self.solution.maxSum([1, 1, 1], 2, 3), 0)
16

17

18
if __name__ == "__main__":
19
    unittest.main()