借助HashMap记录之前的数之和
时间复杂度:o(n) 空间复杂度:o(n)
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); String l1=sc.nextLine(); String l2=sc.nextLine(); int k=Integer.parseInt(l1); char[] nums=l2.toCharArray(); int num=0; long ans=0; //注意:答案数值可能很大,用long防止溢出 HashMap<Integer,Integer> map=new HashMap<>(); map.put(0,1); for(int i=0;i<nums.length;i++){ if(nums[i]=='1') num+=1; if(map.containsKey(num-k)) ans+=map.get(num-k); //累加之前的答案 map.put(num,map.getOrDefault(num,0)+1); } System.out.println(ans); } }