最多允许K次交换的最长子数组
题目描述
给定一个整数数组 nums 和一个整数 k，你可以执行最多 k 次交换操作。每次交换可以交换数组中任意两个位置（下标）的元素。你的目标是：在最多进行 k 次交换的前提下，找到并返回由相同元素组成的最长子数组的长度。
例如：
nums = [1, 2, 2, 1, 2, 1, 1, 2]
k = 2
我们可以通过交换位置，使得某一段连续子数组中所有元素都变成相同数字。比如，我们希望得到全为 2 的最长子数组。一种方法是：交换 nums[0]（值为1）和 nums[4]（值为2），再交换 nums[3]（值为1）和 nums[5]（值为2），得到一段连续的子数组 [2, 2, 2, 2, 2, 2]（从下标1到下标6），长度为6。
注意：我们关心的是“在最多 k 次交换后能得到的、由相同元素构成的最长子数组的长度”，并不需要实际执行交换。
题目保证数组元素均为整数，且 0 <= k <= nums.length。
解题过程循序渐进讲解
这道题的核心是：对于数组中的每个可能的“目标值”（即我们希望子数组全部变成的那个数），计算在最多 k 次交换下，能得到的连续相同目标值子数组的最大长度。
这里“交换”操作等价于“用目标值替换非目标值”，因为我们可以从数组的其他地方拿一个目标值过来交换，但要注意交换会同时影响两个位置。不过，我们可以换一种理解：
在最多
k次交换的限制下，相当于允许将最多k个“非目标值”替换成“目标值”，但前提是这些被替换的非目标值原本所在的位置，在交换后仍然能从其他地方得到目标值来填补。实际上，因为交换是成对的，如果我们有足够多的目标值分布在数组的其他地方，就可以通过交换把它们“搬”到我们想要的区间内。
更简单的思考方式是：
假设我们想得到一段连续区间 [left, right] 内全是目标值 target。设区间内原本有 countTarget 个 target，区间长度为 len = right - left + 1，则区间内非 target 的个数为 len - countTarget。
要想让这个区间全变成 target，我们需要从区间外部拿进 len - countTarget 个 target 来替换这些非 target 的元素。
而从区间外部拿进一个 target 到区间内，必须从区间内拿一个非 target 出去（交换是双向的），所以外部必须有至少 len - countTarget 个可用的 target 供交换。
设整个数组中 target 的总出现次数为 totalTarget，则区间外的 target 个数为 totalTarget - countTarget。
可用的交换次数受两个条件限制：
- 我们最多只能做
k次交换（每次交换可以让区间内增加一个target，同时减少一个非target）。 - 区间外必须有足够的
target来供交换进来，即totalTarget - countTarget >= len - countTarget，简化得totalTarget >= len，即区间长度不能超过数组中该目标值的总个数。
实际上条件2是隐含的：如果 len > totalTarget，即便无限次交换也不可能让长度为 len 的区间全变成 target，因为根本没那么多 target。
所以，对于固定的 target，我们想找一个最长的子数组，使得子数组内“非target的元素个数” ≤ min(k, totalTarget - countTarget) ？不完全是。
更精确的动态规划思路是滑动窗口：
对于每个目标值 target，我们滑动一个窗口 [left, right]，用变量 count 记录窗口内 target 的个数。窗口内“非target的元素个数” = 窗口长度 - count。
我们需要“非target的元素个数” ≤ k，且同时窗口长度 ≤ totalTarget（因为最多只能有 totalTarget 个 target 可用）。
在窗口滑动时，如果窗口长度 - count > k，说明需要交换的次数超过 k 了，则移动左指针。
这样，对于每个 target，我们可以得到满足条件的最长窗口长度，对所有 target 取最大值就是答案。
但是，这里有个细节：滑动窗口时，我们只保证了“非target数 ≤ k”，但没保证窗口外有足够多的 target 用来交换。
如果窗口长度 - count ≤ k，但窗口长度 > totalTarget，这是不可能的，因为根本没那么多 target 来填满窗口。
所以在判断窗口有效性时，还要加条件：窗口长度 ≤ totalTarget。
因为 totalTarget 是固定的，我们可以在找到窗口长度 - count ≤ k 时，用 min(窗口长度, totalTarget) 来更新答案？不对，因为如果窗口长度 > totalTarget，我们不可能填满这么长的窗口，所以能填满的最大长度只能是 totalTarget，但如果我们允许 k 很小，可能连 totalTarget 都填不满。
更严谨的做法是：
设需要交换的次数 need = 窗口长度 - count（即把窗口内非 target 全换成 target 需要的次数），条件是：
- need ≤ k（交换次数限制）
- 窗口长度 ≤ totalTarget（target 总数足够）
如果 need > k，则缩小窗口；否则，用窗口长度更新答案。
因为 totalTarget 是固定的，当 need ≤ k 且窗口长度 ≤ totalTarget 时，窗口长度就是可行的。
算法步骤：
- 统计每个不同数字在数组中出现的总次数 totalCount[value]。
- 对于每个不同的数字 target：
- 初始化 left = 0, count = 0（当前窗口内 target 的数量）。
- 遍历右端点 right 从 0 到 n-1：
- 如果 nums[right] == target，则 count++。
- 窗口长度 len = right - left + 1。
- 需要交换的次数 need = len - count。
- 当 need > k 或者 len > totalCount[target] 时，需要移动左指针：
- 其实 len > totalCount[target] 时，need 必然大于 0 且无法满足，但因为 len 增大才会导致 >totalCount，所以当 len 增加到 totalCount+1 时，need 至少是1，但可能 k 足够大，但 target 不够。实际上，如果 len > totalCount[target]，我们永远无法让这个窗口全变成 target，所以 left 右移直到 len ≤ totalCount[target] 且 need ≤ k。
- 但为了方便，我们可以在 need > k 时左移，然后检查长度是否可行。
- 具体操作：当 need > k 时，左移 left 并更新 count（如果 nums[left]==target 则 count--），直到 need ≤ k。
- 此时，如果 len ≤ totalCount[target]，则用 len 更新答案。
- 返回所有 target 对应的最大长度。
例子验证：
nums = [1,2,2,1,2,1,1,2], k=2
- target=1: totalCount=4
right=0, nums[0]=1, count=1, len=1, need=0 ≤2, len=1≤4 → ans=1
right=1, nums[1]=2, count=1, len=2, need=1 ≤2, len=2≤4 → ans=2
right=2, nums[2]=2, count=1, len=3, need=2 ≤2, len=3≤4 → ans=3
right=3, nums[3]=1, count=2, len=4, need=2 ≤2, len=4≤4 → ans=4
right=4, nums[4]=2, count=2, len=5, need=3 >2 → 移动 left:
left=0, nums[0]=1 → count=1, len=4, need=3 >2 → left=1
left=1, nums[1]=2 → count=1, len=3, need=2 ≤2, len=3≤4 → ans 仍为4
... 最终 target=1 能得到的最长为4（全1子数组长度不超过4，因为只有4个1）。 - target=2: totalCount=4
滑动窗口过程类似，当 right=6 时，窗口 [1,6] 长度6，count=4（下标1,2,4,6是2），need=2 ≤2，且 len=6>totalCount=4，这个窗口不可行（因为没有足够多的2）。但实际上我们不会让 len>totalCount 的窗口被考虑，因为 need>k 时左移了。检查右移过程中：
到 right=6 时，len=6, count=4, need=2，满足 need≤k，但 len=6>4，这时应该左移 left 直到 len≤4 吗？我们的条件判断是：如果 len>totalCount，这个窗口不可能全变成 target，所以应该让 left 右移直到 len≤totalCount。
所以代码中，除了 need>k 时左移，还要在 len>totalCount 时左移。
更统一的处理是：当 len - count > k 或 len > totalCount 时，左移 left。
这样，对于 target=2：
right=5 时，窗口可能是 [1,5] 长度5，count=3（下标1,2,4是2），need=2 ≤k, len=5>4 不满足，左移直到 len=4，然后检查 need。
最终可发现最长是 len=4，但通过交换可以得到更长的吗？
注意：我们允许交换，可以把区间外的 target 交换进来，但 target 总数只有4，所以最长全2子数组长度为4，但数组有4个2，分布在多个位置，通过交换可以让4个2连续，所以答案是4。
但题目例子的答案是6，怎么来的？
我们需要澄清：交换是任意两个位置交换，如果我们想得到连续的2，但数组只有4个2，我们不可能让连续长度超过4。所以例子中给的长度6是怎么做到的？
检查例子：nums = [1,2,2,1,2,1,1,2] 有4个2，4个1。如果想得到全2子数组，最多长度4。但例子说得到长度6，这意味着：他们允许在交换时，把区间外的1换进来，但换进来的1不需要是2，只要区间内全是2即可。
等等，区间内全是2，但区间外是1，我们交换时，从区间外拿一个2进来，把区间内一个1换出去。但区间外必须有2才行。如果区间外没有2了，就不能继续交换。
在例子中，他们交换了两次，得到了6个2连续？但总共只有4个2，不可能有6个2连续。
我怀疑例子中他们得到的是“全为同一个数字”的子数组，可能是1也可能是2。比如把两个1换成了2，使得连续的2增加。但这样需要外部的2。我们看原始数组：
下标:0 1 2 3 4 5 6 7
值: 1 2 2 1 2 1 1 2
目标是全2子数组，我们可以把下标0的1和下标4的2交换，得到：2 2 2 1 2 1 1 1（交换后下标0变成2，下标4变成1）
再把下标3的1和下标7的2交换，得到：2 2 2 2 2 1 1 1（交换后下标3变成2，下标7变成1）
现在从下标0到4是5个2连续，但下标5是1，所以最长连续2的长度是5，不是6。
如果交换不同顺序，可能得到从下标1到6是6个2？我们试一下：
原数组:1 2 2 1 2 1 1 2
先把下标0的1和下标4的2交换：2 2 2 1 1 1 1 2
再把下标3的1和下标7的2交换：2 2 2 2 1 1 1 1
现在从下标0到3是4个2，不是6。
所以长度6似乎不可能。
可能我误解了题目：它允许交换任意两个位置，不一定是区间内外交换。我们可以把区间内的非target和区间外的target交换，但也可以把区间外的非target和区间内的非target交换？不，我们要让区间内全target，只需要把区间内非target换成target，所以必须从区间外拿target进来。
所以区间长度不可能超过target总数。
但例子中给出答案是6，说明目标值可能是1。如果是全1子数组，总共有4个1，也不可能得到6。
看来例子有误，或者我的理解有偏差。实际上，正确的例子应该解释为：我们可以在最多k次交换后，使某个连续子数组全为同一个数字，这个数字可以是数组中的任意数字，但子数组长度受限于该数字的总数和交换次数。
但长度不会超过该数字的总数。
所以正确的解法应该是：
对每个数字target，用滑动窗口，保证窗口内“非target数 ≤ k”且“窗口长度 ≤ target总数”，求最大窗口长度。
修正后的例子：
nums = [1, 2, 2, 1, 2, 1, 1, 2]，k=2
target=1: 总数4，窗口内非1的个数 ≤2 的最大窗口长度：
窗口[0,3] 非1数=1（下标1是2）满足，长度4
窗口[3,6] 非1数=1（下标4是2）满足，长度4
所以最大4。
target=2: 总数4，窗口内非2的个数 ≤2 的最大窗口长度：
窗口[1,4] 非2数=1（下标3是1）满足，长度4
窗口[1,6] 非2数=3（下标3,5,6是1）>2 不满足。
所以最大4。
所以答案是4。
但题目可能希望我们考虑：交换后，子数组内全是同一个数字，这个数字不一定在交换前就在子数组内，我们可以从外部交换进来，但受总数限制。
所以算法是对的。
最终算法步骤：
- 统计每个数字的出现次数，得到 total[val]。
- 初始化 ans = 0。
- 对于每个数字 target：
- 初始化 left = 0, cnt = 0（窗口内 target 的数量）。
- 遍历 right 从 0 到 n-1：
- 如果 nums[right] == target，cnt++。
- 当窗口长度 (right-left+1) - cnt > k 或者 right-left+1 > total[target] 时：
- 如果 nums[left] == target，cnt--。
- left++。
- 更新 ans = max(ans, right-left+1)。
- 返回 ans。
时间复杂度：O(n * d)，其中 d 是不同数字的个数，最坏 O(n^2) 如果所有数字都不同。但数字种类有限时，可接受。
示例运行（修正后）：
nums = [1,2,2,1,2,1,1,2], k=2
target=1: total=4
右指针遍历：
- right=0, cnt=1, len=1, need=0, len≤4 → ans=1
- right=1, cnt=1, len=2, need=1≤2, len≤4 → ans=2
- right=2, cnt=1, len=3, need=2≤2, len≤4 → ans=3
- right=3, cnt=2, len=4, need=2≤2, len=4≤4 → ans=4
- right=4, cnt=2, len=5, need=3>2 → 左移直到 need≤2 且 len≤4 → 最终 left=2, len=3, cnt=1, need=2, ans=4
继续直到结束，ans=4。
target=2: total=4
类似得到 ans=4。
最终结果 4。
再举一例：
nums = [1,1,2,2,1,2,1,2,1], k=2
target=1: total=5
滑动窗口可得到最长长度5（需要交换次数 ≤2 且长度 ≤5）。
边界情况：
- k=0 时，退化为求最长连续相同数字的子数组。
- k ≥ n 时，可以任意交换，答案为最频繁数字的总数。
- 数组为空时，答案为0。
这样就完成了题目的详细讲解。