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

记住这把钥匙:定长窗口加右减左 O(1) 更新和;计数表里不同数的种数==3 才算「全不同」、才更新答案。

先把最左、长度 3 的窗口建起来:第 0 位是 1,加进窗口和、计数表记一笔,现在窗口和是 1、有 1 种不同的数。

先把最左、长度 3 的窗口建起来:第 1 位是 5,加进窗口和、计数表记一笔,现在窗口和是 6、有 2 种不同的数。

先把最左、长度 3 的窗口建起来:第 2 位是 4,加进窗口和、计数表记一笔,现在窗口和是 10、有 3 种不同的数。

第一个长度 3 的窗口 [1, 5, 4] 建好了,和是 10。计数表里有 3 种不同的数,正好等于 3,说明全不同,把它当作目前最大和 ans = 10。

窗口右滑一格。先把右边新进来的 nums[3] = 2 计入:窗口和暂时变成 12,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。

再把左边移出的 nums[0] = 1 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [5, 4, 2] 的和是 11。下一步看这 3 个数有没有重复。

判一下:计数表里有 3 种不同的数,正好 3 种、全不同,而且和 11 比之前的 ans 还大,刷新 ans = 11。

窗口接着右移。先把右边新进来的 nums[4] = 9 计入:窗口和暂时变成 20,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。

再把左边移出的 nums[1] = 5 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [4, 2, 9] 的和是 15。下一步看这 3 个数有没有重复。

判一下:计数表里有 3 种不同的数,正好 3 种、全不同,而且和 15 比之前的 ans 还大,刷新 ans = 15。

再滑一格。先把右边新进来的 nums[5] = 9 计入:窗口和暂时变成 24,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。

再把左边移出的 nums[2] = 4 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [2, 9, 9] 的和是 20。下一步看这 3 个数有没有重复。

判一下:计数表里有 2 种不同的数,不到 3 种,说明有重复(红色标出的就是重复的那些位置),这个窗口不算、直接跳过。

窗口继续右滑。先把右边新进来的 nums[6] = 9 计入:窗口和暂时变成 29,计数表里它的个数加一。这时窗口多了一个,下一步把最左那个吐掉。

再把左边移出的 nums[3] = 2 从窗口和里减掉、计数表里它减一(减到 0 就删键),新窗口 [9, 9, 9] 的和是 27。下一步看这 3 个数有没有重复。

判一下:计数表里有 1 种不同的数,不到 3 种,说明有重复(红色标出的就是重复的那些位置),这个窗口不算、直接跳过。

滑完全程,和最大的那个「k 个互不相同」窗口是 [4, 2, 9],和正好是 15,这就是答案。回头看,我们没给任何窗口重新求和,全靠「加右减左」O(1) 更新,再用计数表的种数判全不同。

边界先想清:无合法窗口得 0、k=n 看整段、k=1 取最大单元素。

面试常考:认出「定长窗口 + 计数判重」模板,以及去掉约束后的退化形态。