本文共 2585 字，大约阅读时间需要 8 分钟。

链接：

大意：

给定一个DNA序列字符串s，字符串中每个字符为'A','C','G'或'T'。现在要求找出在s中连续子串长度为10，且在s中出现过一次以上的所有子串。例子：

思路：

使用两个set。set1用于存放s中所有长度为10的子串，set2用于存放 出现过一次以上的长度为10的子串。

代码：

class Solution {    public List
   
     findRepeatedDnaSequences(String s) {        List
    
      res = new ArrayList<>();        if (s.length() <= 10)            return res;        // set1用于存放所有的长度为10的连续子串 set2用于存放所有出现过一次以上的长度为10的子串        Set
     
       set1 = new HashSet<>(), set2 = new HashSet<>();        for (int i = 0; i + 10 - 1 < s.length(); i++) {            String subStr = s.substring(i, i + 10);            if (set1.contains(subStr))                set2.add(subStr);            set1.add(subStr);        }        res.addAll(set2);        return res;    }}
     
    
   

结果：

结论：

效率不高，有待改进。

改进：

参考：

思路解释参考下方评论 Khaled_Hamdy 老哥。

class Solution{    public List
   
     findRepeatedDnaSequences(String s) {        Set
    
      words = new HashSet<>();        Set
     
       doubleWords = new HashSet<>();        List
      
        rv = new ArrayList<>();        Map
       
         map = new HashMap<>();        // set中存放整数，四个字母每个字母对应0，1，2，3  若set是存放String 则还需要进行一步String->Integer的过程（取哈希值）        map.put('A', 0);map.put('C', 1);map.put('G', 2);map.put('T', 3);        for(int i = 0; i < s.length() - 9; i++) {            int v = 0;            for(int j = i; j < i + 10; j++) {                v <<= 2;                v |= map.get(s.charAt(j));            }            // 如果set添加成功 即set中之前无该元素 返回true  否则返回false  短路与            if(!words.add(v) && doubleWords.add(v)) {                rv.add(s.substring(i, i + 10));            }        }        return rv;    }}
       
      
     
    
   

最佳：

使用位图法（Java中自带BitSet，BitMap类）。主要是提高空间效率

class Solution {    public List
   
     findRepeatedDnaSequences(String s) {        int len = s.length(), mod = 1 << 20, mask = 0xFFFFF, n = 0;        if (len < 11) return new ArrayList<>();                // 'A' -> 0  'C' -> 1 'G' -> 2 'T' -> 3        int[] ints = new int['T' + 1];        ints['C'] = 1; ints['G'] = 2; ints['T'] = 3;        List
    
      list = new ArrayList<>();        BitSet seen = new BitSet(mod), added = new BitSet(mod);        for (int i = 0; i < len; i++) {            n = (n << 2) & mask | ints[s.charAt(i)]; // 获得连续10个字符串的哈希码 （基于上述的字符串->整数映射）            if (i >= 9)                if (seen.get(n)) { // 如果seen中在n位置上已有数字 则返回true 否则返回false                    if (!added.get(n)) {                        added.set(n);                        list.add(s.substring(i - 9, i + 1));                    }                } else seen.set(n);        }        return list;    }}
    
   

转载地址：http://kaesi.baihongyu.com/