1703.得到连续K个1的最少相邻交换次数

链接：1703.得到连续K个1的最少相邻交换次数
难度：Hard
标签：贪心、数组、前缀和、滑动窗口
简介：请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。

题解 1 - cpp

• 编辑时间：2022-12-23
• 执行用时：564ms
• 内存消耗：122.5MB
• 编程语言：cpp
• 解法介绍：[参考链接](https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solution/tu-jie-zhuan-huan-cheng-zhong-wei-shu-ta-iz4v/)。

class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        int ans = 0x7fffffff;
        vector<int> ilist, slist(1, 0);
        for (int i = 0, cnt = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                ilist.push_back(i - cnt++);
                slist.push_back(slist.back() + ilist.back());
            }
        }
        for (int i = 0; i + k <= ilist.size(); i++)
            ans = min(ans, slist[i + k] + slist[i] - 2 * slist[i + k / 2] - k % 2 * ilist[i + k / 2]);
        return ans;
    }
};