2461. 长度为 K 子数组中的最大和#

题目描述#

给你一个整数数组 nums 和一个整数 k。请你找出长度为 k 且所有元素互不相同的子数组的最大和。如果不存在这样的子数组，返回 0。

示例 1：

1
输入：nums = [1,5,4,2,9,9,9], k = 3
2
输出：15
3
解释：长度为 3 的子数组：[1,5,4] 和 10，[5,4,2] 和 11，[4,2,9] 和 15，[2,9,9] 重复元素，[9,9,9] 重复元素。

示例 2：

1
输入：nums = [4,4,4], k = 3
2
输出：0

提示：

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

解法思路#

定长滑动窗口 + 哈希表，要求窗口内元素互不相同。

如何 O(1) 判断「窗口内无重复元素」：用 Counter 记录窗口内每个元素的频次，那么 len(window) 就是窗口内互不相同的元素个数。由于窗口大小固定为 k，len(window) == k 当且仅当窗口内没有重复元素（k 个位置全是不同元素）。

先用前 k 个元素初始化窗口，再用 入-更新-出 三步滑动：

入：右端点 nums[i] 进窗口，更新频次与窗口和 cur；
更新：窗口满 k 时，若 len(window) == k（所有元素互不相同），用 cur 更新最大和 ans；
出：左端点 nums[i-k+1] 出窗口，频次减一（减到 0 则删除键），并从 cur 中扣除。

初值：第一个窗口若含重复元素，则 ans 保持 0（说明至少可以返回 0）。

逐步举例（nums = [1,5,4,2,9,9,9], k = 3）。枚举所有长 3 窗口，只有窗口内无重复才统计：

窗口	不同元素数	是否 ==k	和
[1,5,4]	3	✅	10 → `ans=10`
[5,4,2]	3	✅	11 → `ans=11`
[4,2,9]	3	✅	15 → `ans=15`
[2,9,9]	2	❌ 重复	—
[9,9,9]	1	❌ 重复	—

最大和 ans = 15，与预期一致。可见窗口每右移一位，len(window) 会随进出元素在 1~3 之间波动，只有恰好恢复为 3（无重复）时才参与比较。

与 2841 是同一套路：2841 要求「至少 m 个不同元素」（len(window) >= m），本题是它的特例，要求「全部不同」（len(window) == k）。

复杂度分析#

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

代码实现#

1
from collections import Counter
2

3

4
class Solution:
5
    def maximumSubarraySum(self, nums: list[int], k: int) -> int:
6
        window = Counter(nums[:k])
7
        cur = sum(nums[:k])
8
        ans = cur if len(window) == k 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) == k and cur > ans:
17
                ans = cur
18
        return ans

1
import unittest
2

3

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

8
    def test_example1(self):
9
        self.assertEqual(self.solution.maximumSubarraySum([1, 5, 4, 2, 9, 9, 9], 3), 15)
10

11
    def test_example2(self):
12
        self.assertEqual(self.solution.maximumSubarraySum([4, 4, 4], 3), 0)
13

14
    def test_all_distinct(self):
15
        self.assertEqual(self.solution.maximumSubarraySum([1, 2, 3, 4], 3), 9)
16

17

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