最长全1串

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k,x,s=0,l=1,r=1;
    cin>>n>>k;
    int a[n+1];
    a[0] = 0;
    for(int i=1;i<=n;i++){
        cin>>x;
        a[i] = a[i-1] + x;
    }
    while(r<=n){
        if((r-l+1)-(a[r]-a[l-1])<=k){
            s = max(s, r-l+1);
            r++;
        }else if(l<r)
            l++;
        else{
            l++;
            r++;
        }
    }
    cout<<s<<endl;
    return 0;
}

双指针，时间复杂度O(N)
思路：
用left,right分别表示，满足翻转k次所能达到连续1的起始和结束位置

n,k = map(int, input().split())
l = list(map(int, input().split()))
left, right = 0, 0
res = 0
while right < n:
    if l[right] == 0:
        k -= 1
    if k == 0:
        res = max(res, right - left + 1)
    if k < 0:
        if l[left] == 0:
            k += 1
        left += 1
        while left < right and l[left] == 0:
            left += 1
            k += 1
    right += 1
print(max(res, right-left))

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getAns(arr, N, K);
        System.out.println(res);
    }

    public static int getAns(int[] arr, int N, int K) {
        int left = 0, right = 0, res = 0;
        while (right < N) {
            if (arr[right] == 0)
                K--;
            while (K < 0) {
                if (arr[left] == 0)
                    K++;
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }
}

#include <iostream>
(720)#include <cstdio>
#include <unordered_map>
using namespace std;

const int MAXN=300010;
int num[MAXN];
int num2[MAXN];
unordered_map<int,int> mp;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&num[i]);
    int cont=0;
    int mx=0;
    mp[0]=0;
    for(int i=0;i<n;i++)
    {
        if(num[i]) num2[i]=cont;
        else 
        {
            cont++;
            num2[i]=cont;
            mp[cont]=i;
        }
        if(cont >= k)
        {
            mx=max(mx,i-mp[cont-k]);
        }
        else
        {
            mx=max(mx,i+1);
        }
    }
    printf("%d\n",mx);
    return 0;
}

package main

import (
	"fmt"
)

func main() {
	n, k := 0, 0
	fmt.Scan(&n, &k)
	str := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &str[i])
	}

	right, left, count, res, num := 0, 0, 0, 0, 0
	for ; right < n; right++ {
		if str[right] == 0 {
			num++
			count++
		}
		if count > k {
			if str[left] == 0 {
				count--
			}
			left++
		}
		if count == k && right-left+1 > res {
			res = right - left + 1
		}
	}

	if num <= k {
		res = n
	}
	fmt.Println(res)
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	reader := bufio.NewReader(os.Stdin)
	str, _ := reader.ReadString('\n')
	str = str[:len(str)-1] //去掉换行符
	strSlice := strings.Split(str, " ")
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i], _ = strconv.Atoi(strSlice[i])
	}
	l, r, ans := 0, 0, 0
	for r < n {
		if arr[r] == 1 {
		} else if k > 0 {
			k--
		} else {
			for arr[l] == 1 {
				l++
			}
			l++
		}
		if r-l+1 > ans {
			ans = r - l + 1
		}
		r++
	}
	fmt.Println(ans)
}

#include <iostream>
#include <vector>

int main() {
    int N, K;
    std::cin >> N >> K;
    std::vector<int> nums(N, 0);
    for(int i = 0; i < nums.size(); i++) {
        std::cin >> nums[i];
    }
    
    int left = 0, right = 0;
    int count = 0, maxLen = 0;
    for(; right < nums.size(); right++)
    {
        if(nums[right] == 0) count++;
        
        while(count > K) {
            if(nums[left] == 0) --count;
            left++;
        }
        
        maxLen = std::max(maxLen, right - left + 1);
    }
    
    std::cout << maxLen << std::endl;
    
    return 0;
}

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] bits = new int[n];
        for(int i = 0; i < n; i++){
            bits[i]=sc.nextInt();
        }
        int res = 0;
        int left = 0;
        int right = 0;
        while(left < n && right < n){
            while(right < n && (bits[right]==1 || k > 0)){
                if(bits[right]==0){
                    k--;
                }
                right++;
            }
            res = Math.max(right - left, res);
            if(bits[left]==0){
                k++;
            }
            left++;
        }
        System.out.println(res);
    }
}

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader rf=new BufferedReader(new InputStreamReader(System.in));
        String s;
        while((s=rf.readLine())!=null){
            String[] de=s.split(" ");
            int n=Integer.valueOf(de[0]);
            int k=Integer.valueOf(de[1]);
            if(n<k){
                System.out.println(n);
                return;
            }
            String[] fr=rf.readLine().split(" ");
            int[] res=new int[n];
             
            for(int i=0;i<n;i++){
                res[i]=Integer.valueOf(fr[i]);
            }
            int left=0,right=0;
            int count=0;
            int max=0;
            while(right<n){
                if(res[right]==1){
                    count++;
                }
                if(count+k>=n){
                    System.out.println(n);
                    return;
                }
                if(count+k<right-left+1){
                    max=Math.max(count+k,max);
                    if(left<right){
                        if(res[left]==1){
                            count--;
                        }
                          left++;
                        
                    }
                    while(left<right&&res[left]==0){
                        left++;
                    }
                }
                right++;
            }
             System.out.println(max);
        }
}
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int N = 300010;
int num[N];

int max(int a, int b)
{
	if (a >= b)
		return a;
	else
		return b;
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i<n; i++) 
		cin >> num[i];
	vector<int> Hash(2, 0);
	int res = 0, maxNum = 0;
	for (int i = 0, j = 0; j<n; j++) 
	{
		Hash[num[j]]++;
		maxNum = max(maxNum, Hash[1]); // 这里变为区间中1的个数
		while (j - i + 1 - maxNum>m)
			Hash[num[i++]]--;
		res = max(res, j - i + 1);
	}
	cout << res << endl;
}

最长全1串

思路：维护一个最多有K个0存在的滑动窗口，用窗口中的元素数量（该窗口中所有0都可以变成1）更新答案。

因此，统计【0，i】区间内0的数量，到下标i的映射。i作为滑动窗口的右端点， 通过以下方式计算出滑动窗口的左端点，进而得到窗口内元素的数量(right - left + 1, 闭区间[left, right])。

如果当前0累计出现的次数不大于K次， 则可以将i左侧所有0变成1，左端点为0。

如果当前0累计出现次数（记为count）大于K次，我们只能最多将最近的K个0变成1，前count - k个0 无法变成1, 因此左端点为map.get(count-k) + 1。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0; i < n; i++)  {
            a[i] = sc.nextInt();
        }
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0, count = 0;
        for(int i=0; i < n; i++) {
            if(a[i] == 0) {
                ++count;
                map.put(count, i); // 0的数量：当前位置
            }
            if(count > k) 
                res = Math.max(res, i-map.get(count-k));
            else
                res = Math.max(res, i+1);
        }
        System.out.println(res);
    }
}