187. Repeated DNA Sequences.md

题目

187. Repeated DNA Sequences

思路

412ms 6% 今天可真丑陋

用一个map存储子串出现的次数。然后遍历这个map，找到大于一次的加入到result中。

268ms

添加map元素时不必count了，直接判断如果它的second是否将变成2，如果是那就添加到result中

124ms 45%

采用unordered_map降低一半时间。

100ms 55%

采用set存储结果，而不是vector。 思路二是用二进制。学习一下。

代码

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        if(s.size()<10) return{};
        map<string,int> m;
        vector<string> result;
        string tmp;
        for(int i=0;i<s.size()-9;i++){
            tmp=s.substr(i,10);
            int k=m.count(tmp);
            if(k==0) m.insert({tmp,1});
            else m[tmp]=k+1;
        }
        
        for(auto& p:m){
            if(p.second>1) result.push_back(p.first);
        }
        return result;
    }
};