题解 | #重复的DNA序列#

题目的主要信息：

所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的，例如 'ACTGGGC' 。 请你实现一个函数找出所有的目标子串，目标连续子串的定义是，长度等于 10 ，且在 DNA 序列中出现次数超过 1 次的连续子串。

方法一：

用最直接的方式来查找，遍历一遍DNA序列，枚举所有长度为10的子串，用find函数找到其在DNA序列中第一次出现的位置，如果第一次出现的位置t不是当前遍历的位置，则说明前面出现过，把这个子串和位置信息存入tmp中。之所以存储位置信息是为了保证子串的位置顺序。最后转换为数组返回。

具体做法：

class Solution {
public:
    vector<string> repeatedDNA(string DNA) {
        vector<string> res;
        map<int,string> tmp;//储存子串和位置信息，保证子串的位置
        for(int i=0;i<=DNA.size()-10;++i){
            string s=DNA.substr(i,10);//长度为10的子串
            int first=DNA.find(s);//在DNA中找到第一次出现的位置
            if(first!=i){//如果第一次出现的位置不是当前位置，说明前面出现过
                if(tmp.find(first)==tmp.end()){//放入tmp中
                    tmp.insert(pair<int, string>(first,s));
                }
                
            }
        }
        for(auto iter=tmp.begin();iter!=tmp.end();iter++){//将子串存入res中
            res.push_back(iter->second);
        }
        
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，for循环遍历一遍DNA序列，find函数的时间复杂度为$O(n)O(n)$。
• 空间复杂度：$O(n)O(n)$，res的大小为$O(n)O(n)$。

方法二：

用哈希表tmp储存子串和位置信息，遍历一遍字符串，统计每个子串出现的次数。然后为了保证重复子串的顺序，再遍历一遍字符串，对于出现次数大于1的子串保存到res中，同时在哈希表中删除这一子串的次数信息，防止重复。

具体做法：

class Solution {
public:
    vector<string> repeatedDNA(string DNA) {
        vector<string> res;
        unordered_map<string,int> tmp;//储存子串和次数
        for(int i=0;i<=DNA.size()-10;++i){
            string s=DNA.substr(i,10);//长度为10的子串
            tmp[s]++;//统计次数
        }
        for(int i=0;i<=DNA.size()-10;++i){
            string s=DNA.substr(i,10);//长度为10的子串
            if(tmp[s]>1){//如果出现的次数大于1
                res.push_back(s);//保存到vector中
                tmp.erase(s);
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历字符串。
• 空间复杂度：$O(n)O(n)$，tmp的大小为$O(n)O(n)$。