蓝桥杯2019年第十届真题-人物相关性分析-题解（Java代码）AC

思路：1、找出文本中所有Alice出现的位置，list1记录A的下标，2、找出文本中所有Bob出现的位置，list2记录B的下标. 3、遍历list1找出所有符合条件的Bob的个数. 4、同3再去找Bob之前的符合的Alice个数

import java.util.ArrayList;
import java.util.Scanner;
public class Main
{
    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);
        int K=scan.nextInt();
        scan.nextLine();
        String str=scan.nextLine();
        //保存A B在字符串中出现的位置
        ArrayList<Integer> list1=new ArrayList<>();
        ArrayList<Integer> list2=new ArrayList<>();
        //统计Alice出现的位置 记录的是A的位置
        for(int i=0;i+5<=str.length();i++)
        {
            //判断名字前后不能存在字母
            if((i==0||!check(str.charAt(i-1)))&&(i+5==str.length()||!check(str.charAt(i+5))))
            {
                if(str.substring(i, i+5).equals("Alice"))
                    list1.add(i);
            }
        }
        //统计Bob出现的位置 记录的是B的位置
        for(int i=0;i+3<=str.length();i++)
        {
            //
            if((i==0||!check(str.charAt(i-1)))&&(i+3==str.length()||!check(str.charAt(i+3))))
            {
                if(str.substring(i,i+ 3).equals("Bob"))
                    list2.add(i);
            }
        }
//        for(int i=0;i<list1.size();i++)
//            System.out.print(list1.get(i)+" ");
//        System.out.println();
//        for(int i=0;i<list2.size();i++)
//            System.out.print(list2.get(i)+" ");
        long ans=0;
        //遍历，找出符合条件的Bob的个数
        for(int i=0,l=0,r=-1;i<list1.size();i++)
        {
            while((r+1<list2.size())&&(list1.get(i)>=list2.get(r+1))) 
            {
                r++;
            }
            while((l<=r)&&list1.get(i)-list2.get(l)-2>K) 
            {
                l++;
            }
            ans+=r-l+1;
        }
        //去找Bob前符合的Alice的数量
        for(int i=0,l=0,r=-1;i<list2.size();i++)
        {
            while(r+1<list1.size()&&list2.get(i)>=list1.get(r+1)) 
            {
                r++;
            }
            while((l<=r)&&list2.get(i)-list1.get(l)-4>K) 
            {
                l++;
            }
            if(l!=-1&&r!=-1)
                ans+=r-l+1;
        }
        System.out.println(ans);
        scan.close();
    }
    private static boolean check(char ch)
    {
        return (ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z');
    }
}