力扣刷题记录： 2134. 最少交换次数来组合所有的 1 Ⅱ

        这道题是第275场周赛的 Q2，LC竞赛分为 1748，主要考察滑动窗口。说实话这道题要想到是滑动窗口就很简单，否则就根本无从下手。

方法一. 滑动窗口（时间超过62.53%C++用户）

        处理环形数组的一个很有效的技巧就是 “追加”，把整个nums数组追加到nums数组后面，比如说 1，0，1，1 变成 1，0，1，1，1，0，1，1。这样就可以做到“首尾相接”这一效果。基本上所有环形数组题都可以这么预处理。我们这题也先用追加法预处理数组。

        我们计算原数组含有1的个数total_ones，那么我们的环形数组里所有1相邻的含义就变成了：在完成追加后的新数组里，找到一个长度为total_ones的子数组，这个子数组里全是1。因此交换的次数对应着子数组中含0的个数。只要找到含0个数最小的子数组，其含0的个数就是交换的最小次数。这个子数组的寻找需要用滑动窗口将复杂度降到O(n)，否则会超时。

        这道题关键在于看出它是个滑动窗口，看不出来的话全部白瞎，我觉得思路挺复杂的。

        代码如下：

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        if(nums.size()==1) return 0;

        int n = nums.size();
        for(int i=0;i<n;i++){
            nums.push_back(nums[i]);
        }

        int total_ones = 0;
        for(int i=0;i<n;i++) total_ones += (nums[i]==1);

        int left = 0,right = total_ones -1;
        int tmp=0;
        for(int i=left;i<=right;i++){
            tmp+=(nums[i]==1);
        }
        int res = total_ones-tmp;
        while(right<2*n-1){
            right++;
            left++;
            tmp -= (nums[left-1]==1);
            tmp += (nums[right]==1);
            res = min(res,total_ones-tmp);
        }
        return res;
    }
};