LeetCode 2134 最少交换聚拢所有1题解逻辑疑问

题目规则 #

• 交换（swap）：交换数组中两个不同位置的元素值
• 环形数组（circular array）：数组首元素和尾元素视为相邻
• 题目要求：给定二进制环形数组nums，返回将数组中所有1聚拢到任意连续位置所需的最少交换次数。

参考Java实现 #

class Solution {
    public int minSwaps(int[] nums) {
        // 统计数组中1的总个数
        int cntones=Arrays.stream(nums).sum();
        // 初始化结果为理论最大值，作为比较兜底
        int rslt=nums.length;
        // 统计当前窗口内0的个数，也就是当前窗口需要的交换次数
        int holes = 0;
        // 初始化第一个窗口：从下标0到cntones-1
        for(int i=0;i<cntones;i++) {
            if(nums[i]==0)
                holes++;
        }
        // 用第一个窗口的交换次数更新初始结果
        rslt = Math.min(rslt, holes);
        
        // 初始化滑动窗口右指针，取模兼容边界场景
        int rgt=cntones % nums.length;
        // 滑动遍历所有可能的窗口
        for(int lft=0;lft<nums.length;lft++) {
            rslt=Math.min(rslt,holes);
            if(nums[lft]!=nums[rgt]) 
                if(nums[rgt]==1)
                    holes--;
                else 
                    holes++;
            rgt=(rgt+1)%nums.length;
        }
        return rslt;
    }
}

逐点疑问解答 #

1. 初始值rslt = nums.length的合理性 #

这个值是理论上不可能出现的上界，专门用来做最小值比较的兜底初始值。
这道题的核心结论是：所有1聚拢到连续位置，等价于存在一个长度等于1总个数（cntones）的连续窗口全是1；这个窗口里有多少个0，就需要多少次交换——每个0都要和窗口外的1交换位置，才能填满窗口。
合法场景下需要的交换次数最多是多少？最多是窗口全为0，也就是需要cntones次交换。而cntones的取值范围是0到nums.length：当cntones == nums.length时数组全是1，实际需要交换0次；其余场景cntones < nums.length，需要的交换次数必然小于nums.length。
举个例子，交替排列数组[0,1,0,1]，cntones=2，最坏情况窗口内有2个0，只需要2次交换，远小于数组长度4。把初始值设为nums.length，可以保证第一次比较时，任何合法的窗口交换次数都比它小，不会因为初始值过小导致最终结果计算错误。

2. 首次rslt = Math.min(rslt, holes)的作用 #

你对holes的理解完全正确：它统计的是长度等于cntones的窗口内0的数量，对应该窗口作为1聚拢位置时需要的交换次数。
前面初始化完第一个窗口（下标0到cntones-1）后，这行代码的作用就是把第一个合法窗口的交换次数赋值给rslt，替换掉之前的兜底初始值，作为后续滑动找最小值的基准。

3. rgt = cntones % nums.length取模的作用 #

你说的cntones不会超过nums.length是对的，在数组长度大于1、且cntones < nums.length的普通场景下，取模结果就是cntones，和直接写rgt = cntones效果完全一致。
取模是专门为了覆盖cntones == nums.length的边界场景：

• 场景1：数组全为1，此时cntones = nums.length，如果不取模，rgt值等于数组长度，会触发数组下标越界；取模后结果为0，刚好对应环形数组中窗口跨过首尾的位置，逻辑正确。
• 场景2：单元素数组，比如nums=[0]或nums=[1]，此时cntones要么是0要么是1，取模后rgt都是0，不会出现下标为1的越界问题，和注释提到的兼容单元素测试用例的作用一致。

4. 滑动窗口循环的执行逻辑 #

这个循环的作用是遍历环形数组上所有长度为cntones的连续窗口（包括跨首尾的环形窗口），逐个计算每个窗口需要的交换次数，找到全局最小值：

• 每轮循环对应窗口向右滑动1位：原来的左指针lft指向的元素移出窗口，右指针rgt指向的元素移入窗口
• 循环开头先取当前窗口的holes值和已有最小值rslt比较，更新最小值
• 接着判断移出元素和移入元素的值是否相等：
  • 如果值相等：要么移出0移入0，要么移出1移入1，窗口内0的总数不变，holes不需要修改
  • 如果值不等：若移入的rgt位置值为1，说明移出的是0，窗口内0的数量减1，holes--；若移入的rgt位置值为0，说明移出的是1，窗口内0的数量加1，holes++
• 最后把右指针向后移动1位，通过取模保证下标在环形数组范围内不越界，进入下一轮循环
  整个循环跑完nums.length次后，所有可能的连续窗口就都遍历完成，此时rslt存的就是最少交换次数。

内容的提问来源于stack exchange，提问作者Kang_the_Conqueror