题解 | #DNA序列#

滑动窗口法

长度为n的窗口，在char数组上滑动，记录每次包含的GC数量。

每次滑动时，左边丢了一个，右边加入一个。

可以利用这个特点，用窗口上次位置的GC数量就能计算出，此时GC数量。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String s = in.nextLine();
        char[] chs = s.toCharArray();
        int len = chs.length;

        int l = in.nextInt();
        int[] num = new  int[len - l + 1];
        int max = 0;

        int i = 0;
        int j = l - 1;

        int k = 0;
        while (k <= j) {
            if (chs[k] == 'G' || chs[k] == 'C') {
                max ++;
            }
            k ++;
        }
        num[0] = max;
        //初始化完成

        i++;
        j++;
        while (j < len) {
            int tmp = 0;
            //如果丢掉的那个字符属于GC
            if (chs[i - 1] == 'G' || chs[i - 1] == 'C') {
                tmp --;
            }

            //如果新加的那个字符属于GC
            if (chs[j] == 'G' || chs[j] == 'C') {
                tmp ++;
            }
            num[i] = num[i - 1] + tmp;

            max = max > num[i] ? max : num[i];

            i ++;
            j ++;
        }

        for(int a = 0; a < num.length; a ++){
            if(num[a] == max){
                System.out.println(s.substring(a, a + l));
                break;
            }
        }

    }
}