2134. 最少交换次数来组合所有的 1 II

题目描述

解题思路

设数组中1的数量为len，维护一个长度为len的滑动窗口，从左向右扫描一遍数组，对于每个窗口，需要交换的次数就是窗口中0的数量。 环形数组可以把数组想象成二倍的原数组，使用模运算加以简化，这样i和j就不需要特殊处理了！

代码

class Solution {
public:
    int minSwaps(vector<int>& nums) {

        int n = nums.size();

        int len = 0;//1的数量
        for(auto &x : nums) len += x;

        if(len >= nums.size()) return 0;

        int ans = 0, cnt = 0;//cnt代表1的数量
        for(int i = 0, j = 0; i < len + n; i++)
        {
            cnt += nums[i % n];//扩展有边界
            if(i - j + 1 == len) 
            {
                ans = max(ans, cnt);//问题的逻辑
                cnt -= nums[(j++)%n];//收缩左边界
            }
        }

        return len - ans;
        
    }
};