题目的主要信息：

给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。

方法一：

暴力方法。遍历一遍str的所有长度为len的子串，用max保存其中最大的G、C个数，index用来索引G、C个数最多的子串。遍历每一个子串，统计其中的G、C的个数count，count和max比较，如果count>max，则更新max和index的值。

最后用substr函数、index输出对应的子串。

具体做法：

#include<iostream>

using namespace std;

int main(){
    string str;
    int len;
    while(cin >> str >> len)
    {
        int index = 0, max = 0;
        for(int i = 0; i <= str.size()-len; ++i)//遍历每一个子串
        {
            int count = 0;
            for(int j = i; j < i+len; j++){//统计当前子串中G、C的个数
                if(str[j] == 'G' || str[j] == 'C')
                    count ++;
            }
            if(count > max){//如果当前子串的G、C个数比max大，则更新max的值
                max = count;
                index = i;//更新索引
            }
        }
        cout << str.substr(index, len) << endl;//输出子串
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历所有子串。
空间复杂度： $O (1)$ ,只用了常数空间。

方法二：

滑动窗口的思想。整体思想和方法一类似，但是滑动窗口可以减少子串内部的统计，每次窗口向右移动一格，变化的部分只有首位和末位，少了上一个窗口的首位，多了一个末位，我们只需要看这两个位置CG的变化情况，如果上一个窗口的首位是CG，那么count相对于上一个窗口的count少了1个；如果末位是CG，那么count相对于上一个窗口的count多了1个。更新完count后和max比较，判断是否要更新最大窗口的索引。 alt 具体做法：

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

int main(){
    string str;
    int len;
    cin>>str>>len;
    int max=0;
    int count=0;
    int begin=0;//窗口起始位置
    int end=len-1;//窗口末位置
    map<char,int>map{{'A',0},{'C',1},{'G',1},{'T',0}};//便于快速统计CG数量
    for(int i=0;i<len;i++){//统计第一个窗口中CG的个数用于初始化max
        max+=map[i];
    }
    for(int i=len;i<str.size();i++){//滑动窗口，当前窗口为[i-len+1,i]
        count+=map[str[i]];//str[i]为当前窗口的末位置,判断是否为CG
        count-=map[str[i-len]];//str[i-len]为上一个窗口的起始位置，判断是否为CG
        if(max<count){//更新最大值的信息
            end=i;
            begin=i-len+1;
            max=count;
        }
    }
    cout<<str.substr(begin,len)<<endl;//输出CG个数最多的子串
}

复杂度分析：

时间复杂度： $O (n)$ ，需要滑动n次窗口。
空间复杂度： $O (1)$ ,只用了常数空间。

题解 | #DNA序列#

题目的主要信息：

方法一：

方法二：