有几个PATjava答案

一开始我觉得很简单，连续用了三层遍历，找到P后，再找A，再找T，这样很容易就超时了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
  public static void main(String[] args) throws NumberFormatException, IOException{	  
	  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	  String str=br.readLine();
	  long count=0;//PAT的数量
	  for(int i=0;i<str.length();i++) {
		  if(str.charAt(i)=='P') {
			  for(int j=i;j<str.length();j++) {
				  if(str.charAt(j)=='A') {
					  for(int m=j;m<str.length();m++) {
						  if(str.charAt(m)=='T') {
							  count++;
						  }
					  }
				  }
			  }
		  }
	  }
	  System.out.print(count%1000000007);
  }
}

下面介绍一种做法，先获取到字符串中所有T的数量，再对字符串逐个遍历，遍历到P，P的数量加1，遍历到T那么就把T的数量减1，因为这个T和P还没有A，如果遍历到A，就给total加上P的数量*T的数量

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        char[] s = in.readLine().toCharArray();
        in.close();
        int len = s.length, countp = 0, countt = 0;
        long total = 0;
        for (int i = 0; i < len; i++) {
            if (s[i] == 'T')
                countt++;
        }
        for (int i = 0; i < len; i++) {
            if (s[i] == 'P')
                countp++;
            if (s[i] == 'T')
                countt--;
            if (s[i] == 'A') {
                total = total + countp * countt;
                if (total > 1000000007)
                    total = total % 1000000007;
            }
        }
        System.out.println(total);
    }
}