题目链接
题目描述
给你一个二进制环形数组 nums，返回在任意位置将数组中的所有 1 聚集在一起需要的最少交换次数。
- 交换：选中数组中两个不同位置并交换二者的值。
- 环形数组：第一个元素和最后一个元素相邻。
解法分析：滑动窗口（环形处理）
核心思路
该解法通过滑动窗口技术处理环形数组，核心逻辑如下：
- 窗口大小确定：所有
1聚集在一起时，需要一个长度为w（w是数组中1的总数）的窗口（因为最终所有1会占据连续w个位置）。 - 交换次数的本质：窗口中
0的数量即为需要的交换次数（每个0需被窗口外的1替换，一次交换可解决一个0和一个1的位置）。 - 环形窗口处理：通过将窗口初始化为数组末尾的
w个元素，再滑动窗口覆盖所有可能的连续w个位置（包括跨首尾的环形情况），找到窗口中0数量最少的情况，即为最少交换次数。
代码实现
from typing import List
class Solution:
def minSwaps(self, nums: List[int]) -> int:
w = sum(nums) # 1的总数量，即窗口大小
n = len(nums)
if w == 0 or w == n: # 特殊情况：无1或全是1，无需交换
return 0
# 初始化左指针：指向窗口的最左侧（环形处理，初始窗口为末尾w个元素）
left = -w
# 计算初始窗口中1的数量：窗口为[nums[left], nums[left+1], ..., nums[-1]]
s = sum(nums[i] for i in range(left, 0))
# 初始窗口的交换次数 = 窗口大小 - 窗口中1的数量（即窗口中0的数量）
ans = w - s
# 滑动窗口遍历所有可能的位置（共n种可能，循环n-1次完成所有滑动）
for i in range(n - 1):
# 窗口右移：加入当前i位置的元素，移除left位置的元素
s += nums[i] - nums[left]
# 更新最少交换次数（当前窗口0的数量）
ans = min(ans, w - s)
# 左指针右移，保持窗口大小为w
left += 1
return ans
代码解析
特殊情况处理：
- 若
w = 0（无1）或w = n（全是1），无需交换，直接返回0。
- 若
窗口初始化：
w = sum(nums)：计算数组中1的总数，确定窗口大小为w（所有1聚集后的长度）。left = -w：初始窗口的左边界（负数索引表示从数组末尾开始，如left = -3对应数组倒数第3个元素）。s = sum(nums[i] for i in range(left, 0))：计算初始窗口中1的数量（窗口为[left, -1]，即数组末尾的w个元素）。
初始交换次数：
ans = w - s：窗口中0的数量即为需要的交换次数（每个0需被窗口外的1替换）。
滑动窗口遍历：
- 循环
n-1次（覆盖所有可能的窗口位置）：s += nums[i] - nums[left]：窗口右移，加入当前位置i的元素，移除左边界left的元素，更新窗口中1的数量。ans = min(ans, w - s)：更新最少交换次数（当前窗口0的数量）。left += 1：左边界右移，保持窗口大小为w。
- 循环
返回结果：
- 遍历结束后，
ans即为所有可能窗口中最少的交换次数。
- 遍历结束后，
关键逻辑说明
- 环形数组处理：通过负数索引初始化窗口（指向数组末尾），再通过滑动覆盖所有可能的连续
w个位置（包括跨首尾的情况，如窗口从末尾延伸到开头）。 - 交换次数计算：窗口中
0的数量 = 窗口大小w- 窗口中1的数量s，这部分0必须被窗口外的1替换，因此交换次数等于0的数量。 - 窗口滑动效率：每个元素仅被加入和移除窗口各一次，时间复杂度为
O(n)，适用于大规模数组。
示例详解
以 示例1 为例：nums = [0,1,0,1,1,0,0]
w = sum(nums) = 3（共3个1，窗口大小为3）。n = 7，left = -3，初始窗口为range(-3, 0)即索引-3, -2, -1（对应数组实际索引4,5,6）。- 初始窗口元素：
nums[4]=1, nums[5]=0, nums[6]=0，s = 1 + 0 + 0 = 1，初始交换次数ans = 3 - 1 = 2。
| 循环i | 窗口更新（s） | 当前交换次数（w-s） | ans |
|---|---|---|---|
| i=0 | s += nums[0] - nums[-3] → 1 + 0 - 1 = 0 | 3 - 0 = 3 | 2 |
| i=1 | s += nums[1] - nums[-2] → 0 + 1 - 0 = 1 | 3 - 1 = 2 | 2 |
| i=2 | s += nums[2] - nums[-1] → 1 + 0 - 0 = 1 | 3 - 1 = 2 | 2 |
| i=3 | s += nums[3] - nums[0] → 1 + 1 - 0 = 2 | 3 - 2 = 1 | 1 |
| i=4 | s += nums[4] - nums[1] → 2 + 1 - 1 = 2 | 3 - 2 = 1 | 1 |
| i=5 | s += nums[5] - nums[2] → 2 + 0 - 0 = 2 | 3 - 2 = 1 | 1 |
最终 ans = 1，与示例输出一致。
复杂度分析
- 时间复杂度：
O(n)，其中n是数组长度。初始化窗口和滑动窗口均为线性遍历，每个元素操作O(1)。 - 空间复杂度：
O(1)，仅使用常数级额外空间。
总结
该解法通过滑动窗口高效处理环形数组，核心优势在于：
- 环形覆盖：通过负数索引初始化窗口，结合滑动遍历所有可能的连续
w个位置，完美处理环形特性。 - 交换次数转化：将问题转化为求窗口中
0的最小数量，逻辑清晰且计算高效。 - 线性效率：
O(n)时间复杂度，适用于n达10^5的大规模输入。
这是处理“环形数组中聚集元素”问题的经典方法，滑动窗口结合环形索引处理的思路可推广到类似场景（如环形数组中聚集 0 或其他元素）。