难度: Hard
给你一个整数数组 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 <= 105nums[i] 要么是 0 ，要么是 1 。1 <= k <= sum(nums)运行时间: 152 ms
内存: 25.6 MB
class Solution:
def minMoves(self, nums: List[int], k: int) -> int:
p=[val-i for i,val in enumerate(i for i,val in enumerate(nums) if val)]
s=list(accumulate(p,initial=0))
return min(s[i]+s[i+k]-2*s[i+k//2]-p[i+k//2]*(k%2) for i in range(len(p)+1-k))
首先，题解通过一种转换，将问题简化为寻找连续k个位置的最小距离和。解法的核心在于用一个列表p记录下数组nums中所有1的位置，但减去其索引值以消除非连续1的影响。接着，使用前缀和数组s来方便计算任意段的和。最后，遍历这个前缀和数组s，通过一个滑动窗口的方式来找到使连续k个1距离和最小的起始点。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def minMoves(self, nums: List[int], k: int) -> int:
# 列表p记录nums中所有1的位置减去其索引，以消除非连续性的影响
p = [val - i for i, val in enumerate(i for i, val in enumerate(nums) if val)]
# 计算p的前缀和，方便快速计算区间和
s = list(accumulate(p, initial=0))
# 通过滑动窗口查找最小的距离和
return min(s[i] + s[i + k] - 2 * s[i + k // 2] - p[i + k // 2] * (k % 2) for i in range(len(p) + 1 - k))
在解决问题时，我们需要将一组连续的1移动至一起。数组p通过记录每个1的位置减去其索引值，实际上是为了消除由于1之间的间隔带来的影响，使得每个1都可以视为是连续的。这种转换允许我们直接通过计算这些转换后的位置的中位数来最小化总的移动距离，即移动到中位数位置的总成本最低。
前缀和数组s是通过累加数组p的元素来构建的。其作用是为了快速计算任意连续子数组的和，这在求解问题时至关重要。使用前缀和，我们可以在常数时间内计算得到任意段的和，这大大提高了求解连续k个1的最小距离和的效率。
这个表达式是通过数学推导和优化得到的。它的核心在于找到连续k个1的中间点，使得到这个点的距离之和最小。这个中间点位于i到i+k的中间，即`i + k // 2`。表达式通过计算以这个中点为目标的总距离来实现。`s[i] + s[i + k]`是获取区间i到i+k的1的位置总和，`2 * s[i + k // 2]`是两倍的中间点之前的位置和，用于从总和中减去，`p[i + k // 2] * (k % 2)`处理k为奇数时中间点的额外计算。
选择滑动窗口大小为k是因为我们需要计算连续k个1的位置。使用滑动窗口方法可以在一次遍历中通过移动窗口边界来更新求解，这样既保证了算法的效率，又能确保找到所有可能的k个连续1的情况进行比较，从而找到最小距离和。这种方法因其高效的时间复杂度而被采用，对于较大数据集也能快速求解。