题解 | #重复的DNA序列#

哈希

• umap存放字符串第一次出现的首字符下标
• umap1存放重复出现的字符串 并且map自带自带 key 的升序排列，解决先后问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串vector
     */
    vector<string> repeatedDNA(string DNA) {
        // write code here
        if(DNA.length()<10)return {};
        if(DNA.length()==10)return {DNA};
        vector<string>ans;
        map<string, int>umap;
      	map<int, string>umap1;
        string s = DNA.substr(0, 10);
        umap[s]=0;
        for(int i=1; i<=DNA.length()-10; i++){
            s = DNA.substr(i, 10);
            if(umap.count(s) && !umap1.count(umap[s])){
                umap1[umap[s]] = s;
            }
            else umap[s] = i;
        }
        for(auto it=umap1.begin(); it!=umap1.end(); it++){
            ans.push_back(it->second);
        }
        return ans;
    }
};