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

🟡 中等 https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/description/

逆天思路

百思不得其解。最后看答案：可以先计算数组中的所有1的和，确定一个窗口的大小就是数组的和，然后滑动窗口内的0一定要被换掉，我们不需要直到和谁换但一定要换，因此可以得到所有情况的交换情况。

代码

class Solution {

public:

    int minSwaps(vector<int>& nums) {

        int sum = accumulate(nums.begin(),nums.end(),0);

        if(sum==0) return 0;

        int window_sum = 0;

        for(int i = 0;i<=sum-2;i++){

            window_sum +=nums[i];

        }

        int res = nums.size();

        for(int i = sum-1;i<=nums.size()+sum-2;i++){

            window_sum+=nums[i%nums.size()];

            res = min(res,sum-window_sum);

            window_sum-=nums[i-sum+1];

        }

        return res;

    }

};