2023-09-30：用go语言，给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1， 每一次移动，你

2023-09-30：用go语言，给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1，

每一次移动，你可以选择 相邻 两个数字并将它们交换。

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

输入：nums = [1,0,0,1,0,1], k = 2。

输出：1。

来自左程云。

答案2023-09-30：

步骤描述：

1.定义一个函数 minMoves(nums []int, k int)，传入一个整数数组 nums 和一个整数 k。

2.如果 k 等于 1，直接返回 0。

3.获取数组 nums 的长度 n。

4.计算目标窗口中索引和的左半部分，即 (k - 1)/2 个索引的和，赋值给 leftAimIndiesSum。

5.计算目标窗口中索引和的右半部分，即 (k-1)*k/2 - leftAimIndiesSum，赋值给 rightAimIndiesSum。

6.初始化一个变量 ans，并将其赋值为最大整数。

7.初始化左边窗口的起始索引 l 为 0，中间位置索引 m 为 (k - 1)/2，右边窗口的结束索引 r 为 k - 1。

8.计算左边窗口需要的 1 的个数 leftNeedOnes 为 (k - 1)/2 + 1。

9.初始化左边窗口的起始索引 leftWindowL 为 0，左边窗口的 1 的个数 leftWindowOnes 为 0，左边窗口中索引和的总和 leftWindowOnesIndiesSum 为 0。

10.遍历数组 nums，i 从 0 到 m-1，进行如下操作：

10.1.如果 nums[i] 等于 1，将 leftWindowOnes 加一，leftWindowOnesIndiesSum 加上 i。

11.计算右边窗口需要的 1 的个数 rightNeedOnes 为 k - leftNeedOnes。

12.初始化右边窗口的结束索引 rightWindowR 为 m，右边窗口的 1 的个数 rightWindowOnes 为 nums[m]，右边窗口中索引和的总和 rightWindowOnesIndiesSum 为 0。

13.如果 nums[m] 等于 1，将 rightWindowOnesIndiesSum 赋值为 m。

14.对于 l、m、r 从初始状态开始，进行如下操作：

14.1.如果 nums[m] 等于 1，将 leftWindowOnes 加一，leftWindowOnesIndiesSum 加上 m，rightWindowOnes 减一，rightWindowOnesIndiesSum 减去 m。

14.2.当 leftWindowOnes 大于 leftNeedOnes 时，如果 nums[leftWindowL] 等于 1，则将 leftWindowOnes 减一，leftWindowOnesIndiesSum 减去 leftWindowL，左窗口的起始索引 leftWindowL 加一。

14.3.当 rightWindowOnes 小于 rightNeedOnes 且 rightWindowR+1 小于 n 时，如果 nums[rightWindowR+1] 等于 1，则将 rightWindowOnes 加一，rightWindowOnesIndiesSum 加上 rightWindowR+1，右窗口的结束索引 rightWindowR 加一。

14.4.如果左窗口的 1 的个数等于 leftNeedOnes，右窗口的 1 的个数等于 rightNeedOnes，说明找到了满足要求的窗口。将 ans 更新为 leftAimIndiesSum 减去 leftWindowOnesIndiesSum，再加上 rightWindowOnesIndiesSum 减去 rightAimIndiesSum 和 ans 中的较小值。

14.5.更新 leftAimIndiesSum 为 m+1-l，更新 rightAimIndiesSum 为 r-m。

14.6.将 l 加一，m 加一，r 加一。

15.返回 ans。

总的时间复杂度：根据代码逐行分析，其中的遍历是线性时间复杂度 O(n)，其余操作的时间复杂度均为常数时间复杂度。所以总的时间复杂度为 O(n)。

总的额外空间复杂度：除了函数调用栈外，代码中没有使用额外空间，所以额外空间复杂度为 O(1)。

go完整代码如下：

package main

import (

"fmt"

)

func minMoves(nums []int, k int) int {

if k == 1 {

return 0

}

n := len(nums)

x := (k - 1) / 2

leftAimIndiesSum := x * (x + 1) / 2

rightAimIndiesSum := int((k-1)*k/2 - leftAimIndiesSum)

ans := int(^uint(0) >> 1)

l := 0

m := (k - 1) / 2

r := k - 1

leftNeedOnes := m + 1

leftWindowL := 0

leftWindowOnes := 0

leftWindowOnesIndiesSum := 0

for i := 0; i 

if nums[i] == 1 {

leftWindowOnes++

leftWindowOnesIndiesSum += i

}

}

rightNeedOnes := k - leftNeedOnes

rightWindowR := m

rightWindowOnes := nums[m]

rightWindowOnesIndiesSum := 0

if nums[m] == 1 {

rightWindowOnesIndiesSum = m

}

for ; r 

if nums[m] == 1 {

leftWindowOnes++

leftWindowOnesIndiesSum += m

rightWindowOnes--

rightWindowOnesIndiesSum -= m

}

for leftWindowOnes > leftNeedOnes {

if nums[leftWindowL] == 1 {

leftWindowOnes--

leftWindowOnesIndiesSum -= leftWindowL

}

leftWindowL++

}

for rightWindowOnes 

if nums[rightWindowR+1] == 1 {

rightWindowOnes++

rightWindowOnesIndiesSum += rightWindowR + 1

}

rightWindowR++

}

if leftWindowOnes == leftNeedOnes && rightWindowOnes == rightNeedOnes {

ans = min(ans, leftAimIndiesSum-leftWindowOnesIndiesSum+rightWindowOnesIndiesSum-rightAimIndiesSum)

}

leftAimIndiesSum += m + 1 - l

rightAimIndiesSum += r - m

}

return ans

}

func min(a, b int) int {

if a 

return a

}

return b

}

func main() {

nums := []int{1, 0, 0, 1, 0, 1}

k := 2

result := minMoves(nums, k)

fmt.Println(result)

}

在这里插入图片描述rust完整代码如下：

fn min_moves(nums: Vec, k: i32) -> i32 {

if k == 1 {

return 0;

}

let n = nums.len() as i32;

let x = (k - 1) / 2;

let mut left_aim_indices_sum = x * (x + 1) / 2;

let mut right_aim_indices_sum = (k - 1) * k / 2 - left_aim_indices_sum;

let mut ans = std::i32::MAX;

let (mut l, mut m, mut r) = (0, (k - 1) / 2, k - 1);

let left_need_ones = m + 1;

let (mut left_window_l, mut left_window_ones, mut left_window_ones_indices_sum) = (0, 0, 0);

for i in 0..m {

if nums[i as usize] == 1 {

left_window_ones += 1;

left_window_ones_indices_sum += i as i32;

}

}

let right_need_ones = k - left_need_ones;

let (mut right_window_r, mut right_window_ones, mut right_window_ones_indices_sum) = (

m,

nums[m as usize],

if nums[m as usize] == 1 { m as i32 } else { 0 },

);

while r 

if nums[m as usize] == 1 {

left_window_ones += 1;

left_window_ones_indices_sum += m as i32;

right_window_ones -= 1;

right_window_ones_indices_sum -= m as i32;

}

while left_window_ones > left_need_ones {

if nums[left_window_l] == 1 {

left_window_ones -= 1;

left_window_ones_indices_sum -= left_window_l as i32;

}

left_window_l += 1;

}

while right_window_ones 

if nums[(right_window_r + 1) as usize] == 1 {

right_window_ones += 1;

right_window_ones_indices_sum += (right_window_r + 1) as i32;

}

right_window_r += 1;

}

if left_window_ones == left_need_ones && right_window_ones == right_need_ones {

ans = ans.min(

left_aim_indices_sum - left_window_ones_indices_sum + right_window_ones_indices_sum

- right_aim_indices_sum,

);

}

left_aim_indices_sum += (m + 1 - l) as i32;

right_aim_indices_sum += (r - m) as i32;

l += 1;

m += 1;

r += 1;

}

ans

}

fn main() {

let nums = vec![1, 0, 0, 1, 0, 1];

let k = 2;

let result = min_moves(nums, k);

println!("{}", result);

}

在这里插入图片描述c++完整代码如下：

#include 

#include 

using namespace std;

int minMoves(vector& nums, int k) {

if (k == 1) {

return 0;

}

int n = nums.size();

int x = (k - 1) / 2;

int leftAimIndiesSum = x * (x + 1) / 2;

int rightAimIndiesSum = (k - 1) * k / 2 - leftAimIndiesSum;

int ans = INT_MAX;

int l = 0;

int m = (k - 1) / 2;

int r = k - 1;

int leftNeedOnes = m + 1;

int leftWindowL = 0;

int leftWindowOnes = 0;

int leftWindowOnesIndiesSum = 0;

for (int i = 0; i 

if (nums[i] == 1) {

leftWindowOnes++;

leftWindowOnesIndiesSum += i;

}

}

int rightNeedOnes = k - leftNeedOnes;

int rightWindowR = m;

int rightWindowOnes = nums[m];

int rightWindowOnesIndiesSum = nums[m] == 1 ? m : 0;

for (; r 

if (nums[m] == 1) {

leftWindowOnes++;

leftWindowOnesIndiesSum += m;

rightWindowOnes--;

rightWindowOnesIndiesSum -= m;

}

while (leftWindowOnes > leftNeedOnes) {

if (nums[leftWindowL] == 1) {

leftWindowOnes--;

leftWindowOnesIndiesSum -= leftWindowL;

}

leftWindowL++;

}

while (rightWindowOnes 

if (nums[rightWindowR + 1] == 1) {

rightWindowOnes++;

rightWindowOnesIndiesSum += rightWindowR + 1;

}

rightWindowR++;

}

if (leftWindowOnes == leftNeedOnes && rightWindowOnes == rightNeedOnes) {

ans = min(ans,

leftAimIndiesSum - leftWindowOnesIndiesSum + rightWindowOnesIndiesSum - rightAimIndiesSum);

}

leftAimIndiesSum += m + 1 - l;

rightAimIndiesSum += r - m;

}

return ans;

}

int main() {

vector nums = { 1, 0, 0, 1, 0, 1 };

int k = 2;

int result = minMoves(nums, k);

cout 

return 0;

}

在这里插入图片描述c完整代码如下：

#include 

#include 

int minMoves(int* nums, int numsSize, int k) {

if (k == 1) {

return 0;

}

int x = (k - 1) / 2;

int leftAimIndiesSum = x * (x + 1) / 2;

int rightAimIndiesSum = ((k - 1) * k / 2 - leftAimIndiesSum);

int ans = INT_MAX;

int l = 0;

int m = (k - 1) / 2;

int r = k - 1;

int leftNeedOnes = m + 1;

int leftWindowL = 0;

int leftWindowOnes = 0;

int leftWindowOnesIndiesSum = 0;

for (int i = 0; i 

if (nums[i] == 1) {

leftWindowOnes++;

leftWindowOnesIndiesSum += i;

}

}

int rightNeedOnes = k - leftNeedOnes;

int rightWindowR = m;

int rightWindowOnes = nums[m];

int rightWindowOnesIndiesSum = nums[m] == 1 ? m : 0;

for (; r 

if (nums[m] == 1) {

leftWindowOnes++;

leftWindowOnesIndiesSum += m;

rightWindowOnes--;

rightWindowOnesIndiesSum -= m;

}

while (leftWindowOnes > leftNeedOnes) {

if (nums[leftWindowL] == 1) {

leftWindowOnes--;

leftWindowOnesIndiesSum -= leftWindowL;

}

leftWindowL++;

}

while (rightWindowOnes 

if (nums[rightWindowR + 1] == 1) {

rightWindowOnes++;

rightWindowOnesIndiesSum += rightWindowR + 1;

}

rightWindowR++;

}

if (leftWindowOnes == leftNeedOnes && rightWindowOnes == rightNeedOnes) {

ans = min(ans, leftAimIndiesSum - leftWindowOnesIndiesSum + rightWindowOnesIndiesSum - rightAimIndiesSum);

}

leftAimIndiesSum += m + 1 - l;

rightAimIndiesSum += r - m;

}

return ans;

}

int main() {

int nums[] = { 1, 0, 0, 1, 0, 1 };

int k = 2;

int numsSize = sizeof(nums) / sizeof(nums[0]);

int result = minMoves(nums, numsSize, k);

printf("%d\n", result);

return 0;

}

在这里插入图片描述