来源：力扣（LeetCode）

描述：

给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻 两个数字并将它们交换。

请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。

示例 1：

输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。

示例 2：

输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。

示例 3：

输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。

提示：

• 1 <= nums.length <= 10⁵
• nums[i] 要么是 0 ，要么是 1 。
• 1 <= k <= sum(nums)

方法：贪心 + 前缀和

思路

设数组 nums 的长度为 n，其中共有 m 个 1，它们在数组 nums 中的下标分别为 p₀, p₁, ,…, p_m−1 。假设经过若干次交换后，数组 nums 中形成的 k 个连续的 1 的下标为 q, q + 1, …, q + k − 1。根据贪心的思想，要想交换次数最少，必须满足以下两个条件：

• 这 k 个连续的 1 的起始下标在 p 数组中是连续的，即下标为 p_i , p_i+1 ,…, p_i+k−1 。
• k 个 1 的起始下标和结尾下标是按顺序对应的，即下标为 p_i 的 1 交换到 q，下标为 p_i+k−1 的 1 交换到 q + k - 1 ，中间的元素也需要按照顺序。

代码:

class Solution {
public:int minMoves(vector& nums, int k) {vector g;vector preSum(1, 0);for (int i = 0; i < nums.size(); i++) {if (nums[i] == 1) {g.emplace_back(i - g.size());preSum.emplace_back(preSum.back() + g.back());}}int m = g.size(), res = INT_MAX;for (int i = 0; i <= m - k; i++) {int mid = i + k / 2;res = min(res, (1 - k % 2) * g[mid] +  \(preSum[i + k] - preSum[mid + 1]) - \(preSum[mid] - preSum[i]));}return res;}
};

执行用时：100 ms, 在所有 C++ 提交中击败了89.80%的用户
内存消耗：122.6 MB, 在所有 C++ 提交中击败了14.96%的用户
复杂度分析
时间复杂度： O(n)，其中 n 是数组 nums 的长度。
空间复杂度： O(n)。
author：LeetCode-Solution