题解 | #重复的DNA序列#

题目的主要信息：

• 一串只由ATCG字母组成的字符串，求其中出现次数超过1的长度为10的片段
• 输出顺序需要按照在原始字符串中第一次的出现顺序

方法一：暴力查找

具体做法：

字符串的find函数，查找出子串在原串中是否出现，如果查找到了返回的就是该子串第一次出现的位置。因此我们可以遍历字符串所有长度为10的子串，然后在原串中查找它出现的位置，如果它出现的位置不是现有子串的位置，说明前面出现过了，这个子串就是出现次数超过1的，我们可以记录输出它。

但是，又要面临一个去重和输出顺序的问题，因此可以使用容器map，key值记录第一次出现的下标，map就会按照下标排序，同时如果相同下标出现还会自动去重，value值则记录相应的字符子串。统计完成后，遍历map即可得到输出序列。

class Solution {
public:
    vector<string> repeatedDNA(string DNA) {
        vector<string> res;
        map<int, string> mp; //记录重复片段第一次出现的位置和片段
        for(int i = 0; i <= DNA.size() - 10; i++){ //遍历所有长度为10的片段
            string s = DNA.substr(i, 10); 
            int pos = DNA.find(s); //查找该片段第一次出现的位置
            if(pos != i) //如果该片段第一次出现是在此处，说明前面出现过了
                mp.insert({pos, s}); //将前面第一次出现的位置和片段插入map
        }
        for(auto iter = mp.begin(); iter != mp.end(); iter++) //map会对位置排序，遍历将片段取出即可
            res.push_back(iter->second);
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，外循环遍历一次数组，内循环find函数的复杂度为$O(10n)O(10n)$，map的插入为$O(lo{g}_{2}n)O(log\_2n)$，因此总复杂度为$O(n^2)O(n^2)$
• 空间复杂度：$O(n)O(n)$，map最大的空间为不同子串的个数，最坏情况下都不同

方法二：哈希表

具体做法：

上述使用find函数的查找太耗费时间了，我们可以使用哈希表直接去重计数，只需要将unordered_map的key值设置为字符串子串，value值设置为出现次数，第一次遍历所有的子串统计出现次数。第二次还是遍历所有的子串，不能直接遍历哈希表，因为哈希表中位置是不一定的，输出需要按照子串第一次出现的位置来，因此还是遍历原串的所有子串，查询其在哈希表中的次数，如果次数大于1，记录输出，同时从哈希表中将其删除，避免后续再次遇到了，重复输出。

class Solution {
public:
    vector<string> repeatedDNA(string DNA) {
        vector<string> res;
        unordered_map<string, int> mp; //使用哈希表统计长度为10的片段出现次数
        for(int i = 0; i <= DNA.size() - 10; i++){ //遍历每个长度为10的片段
            string s = DNA.substr(i, 10);
            mp[s]++; //统计次数
        }
        for(int i = 0; i <= DNA.size() - 10; i++){ //再次遍历每个长度为10的片段，因为输出要按照位置
            string s = DNA.substr(i, 10);
            if(mp[s] > 1){ //遇到出现次数大于1的片段，将其加入输出
                res.push_back(s);
                mp.erase(s); //删去，防止后续再次加入
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，单独遍历两次字符串，哈希表的操作都是$O(1)O(1)$
• 空间复杂度：$O(n)O(n)$，哈希表的大小最坏情况下为$n-10n-10$