スライドする

Example 1:
Input: nums = [1,0,0,1,0,1], k = 2
Output: 1
Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.

Example 2:
Input: nums = [1,0,0,0,0,0,1,1], k = 3
Output: 5
Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].

Example 3:
Input: nums = [1,1,0,1], k = 2
Output: 0
Explanation: nums already has 2 consecutive 1's.

Constraints:
1 <= nums.length <= 105
nums[i] is 0 or 1.
1 <= k <= sum(nums)

from typing import List
class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        if k<=1: return 0

        #记录所有1的index
        one_ind = []
        length = len(nums)
        for i in range(length):
            if nums[i] == 1:
                one_ind.append(i)

        # sliding window
        # left, right, mid
        # 不断寻找下一个这样的窗口: 窗口里面恰有k个1，
        # 并记录每个窗口对应的move数， 最后返回最小的move数

        # 移动left，right至第一个1处
        right = left = one_ind[0]

        # mid为k个1中正中间的那个1，mid左边的0应向左移出窗口，mid右边的0应向右移出窗口
        mid = k // 2   # 第$mid+1$个1为中间的1
        l_ind = 0  #! 记录left是第几个1，则index of mid = l_ind + mid 

        count = 1   #计数当前窗口1的数量

        ret = float("inf")
        while right < length-1:

            right += 1
            if nums[right] == 0: continue

            count +=1
            # 这里意味着我们找到了下一个1，检查窗口是否已有k个1

            # 若找到了k个1，则记录当前窗口需要的move数
            if count == k:
                # 确定mid_ind:
                mid_ind = one_ind[l_ind+mid]

                # mid及mid左边的0向左移除窗口，mid右边的0向右移除窗口
                # 算法： 从left到right遍历， 记录每个0当前的index1和移除窗口后的index2，
                # 则这个0的交换次数 = |index1-index2|

                # indices := [(index1,index2)...]: a list of two indices of each 0
                # temp1 := left,left+1,left+2... temp2 = right,right-1,right-2
                # 例如： 110010011, k=5 => 001111100, 左边的0移除后的index为0,1;右边的为7,8
                temp1 = left
                temp2 = right
                indices=[]

                for i in range(left,mid_ind):
                    if nums[i] ==0:
                        indices.append((i,temp1))
                        temp1 += 1
                for i in range(right,mid_ind,-1):
                    if nums[i] == 0:
                        indices.append((i,temp2))
                        temp2 -= 1
                # 求move数
                move_num = sum([abs(a-b) for (a,b) in indices])

                # 更新ret
                ret = min(ret,move_num)

                #! 此时向右移动right已无意义，应将left右移至下一个1处
                l_ind +=1
                left = one_ind[l_ind]

                count -= 1

            # 若还不够k个1，则继续寻找

        return ret