一、题目

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数
难度：中等
链接：最少交换次数来组合所有的 1

二、示例

示例1

输入：[1,0,1,0,1]
输出：1
解释：
有三种可能的方法可以把所有的 1 组合在一起：
[1,1,1,0,0]，交换 1 次；
[0,1,1,1,0]，交换 2 次；
[0,0,1,1,1]，交换 1 次。
所以最少的交换次数为 1。

示例 2：

输入：[0,0,0,1,0]
输出：0
解释：
由于数组中只有一个 1，所以不需要交换。

示例 3：

输入：[1,0,1,0,1,0,0,1,1,0,1]
输出：3
解释：
交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

三、解答

（一）错误：超出时间限制

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        num1=data.count(1)
        NumWin=len(data)-num1+1
        num2 = [0]*(NumWin)
        answer = 0
        
        if num1 == 1:
            answer =0
        else:
            for i in range(NumWin):
                num2[i]=data[i:i+num1].count(1)
                answer = num1-max(num2)
            
        return answer
        

（二）正解：滑动窗口

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        num1=data.count(1)
        NumWin=len(data)-num1+1
        num2 = [0]*(NumWin)
        answer = 0
        
        if num1 == 1:
            answer =0
        else:
            num2[0]=data[0:num1].count(1)
            for i in range(1,NumWin):
                num2[i]=num2[i-1]-data[i-1]+data[i+num1-1]
            answer = num1-max(num2)
            
        return answer