题目描述（中等难度）

一个 DNA 序列，从任意位置开始的连续 10 个字母当做一组，将重复的组输出。

解法一

先来个暴力的方法，双层循环，选取一组然后和后边的所有组进行比较，如果发现重复的组就把它加入到结果中。为了防止加入重复的结果，我们用 set 进行存储。

public List<String> findRepeatedDnaSequences(String s) { int len = s.length(); Set<String> res = new HashSet<>(); for (int i = 0; i <= len - 10; i++) { for (int j = i + 1; j <= len - 10; j++) { if (s.substring(i, i + 10).equals(s.substring(j, j + 10))) { res.add(s.substring(i, i + 10)); break; } } } return new ArrayList<>(res); } 

意料之中，超时了。

由于每一组都遍历了两次，所以造成了时间的浪费。我们可以利用一个 HashSet ，每遍历一组就将其放入，在加入之前判断 HashSet 中是否存在，如果存在就说明和之前的发生重复，就把它加到结果中。从而我们可以减少一层循环。

public List<String> findRepeatedDnaSequences(String s) { int len = s.length(); Set<String> res = new HashSet<>(); Set<String> set = new HashSet<>(); for (int i = 0; i <= len - 10; i++) { String key = s.substring(i, i + 10); //之前是否存在 if (set.contains(key)) { res.add(key); } else { set.add(key); } } return new ArrayList<>(res); } 

解法二

正常情况下到解法一就可以结束了，然后在 Discuss 中逛了一下，其实上边的算法还有优化的地方，下边分享一下，参考了 这里)。

通过这句代码 String key = s.substring(i, i + 10);，我们每次截取字符串作为 key 然后存放到 HashSet 中。

对于 Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"。 当 i 等于 0 的时候，key = AAAAACCCCC 当 i 等于 1 的时候，key = AAAACCCCCA 当 i 等于 2 的时候，key = AAACCCCCAA 

我们会发现，递增过程中，每次的字符串相对于之前都是少一个字母，多一个字母，而剩下的 9 个字母是没有变化的。

但是我们的代码中，并没有考虑之前已经得到的字符串，每次都是一股脑的重新从 i 取到 i+9，String key = s.substring(i, i + 10);。那么怎么利用之前的信息呢？

把字符串编码为数字序列，然后通过移位保留之前的信息，具体的看下边的介绍。

我们把字母映射到二进制位， A -> 00, C -> 01, G -> 10, T -> 11，我们可以用一个 HashMap 去存这些对应关系，但因为我们只需要从存 4 个值，我们可以直接用一个 char 数组完成字母到数字的映射。

//因为有 26 个字母，然后我们减去'A'以后，不管字母是什么，下标最大也就是 25 char map[] = new char[26]; map['A' - 'A'] = 0; //二进制 00 map['C' - 'A'] = 1; //二进制 01 map['G' - 'A'] = 2; //二进制 10 map['T' - 'A'] = 3; //二进制 11 

有了这个对应关系我们就可以把字符串映射为二进制序列。

对于 Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"。 就可以看做是 0000000000010101010100000000000010101010100000000000101010111111 当 i 等于 0 的时候，key = AAAAACCCCC 当 i 等于 1 的时候，key = AAAACCCCCA 当 i 等于 2 的时候，key = AAACCCCCAA 就可以看做是 当 i 等于 0 的时候，key = 00000000000101010101 当 i 等于 1 的时候，key = 00000000010101010100 当 i 等于 2 的时候，key = 00000001010101010000 

i = 0 时候的 key 只需要左移两位，把最高位两位去掉，低位腾出两位，然后加上新加入的字母 A，也就是 00，就到了 i = 1 时候的 key。

此外，如果我们的 key 用 int 存储，一般情况下是 32 位的，但我们是 10 个字母，每个字母对应两位，所以我们只需要 20 位，我们需要把 key 和 11111111111111111111(0xfffff) 进行按位与，只保留低 20 位，所以更新 key 的话需要三个步骤，左移两位 -> 加上当前的字母 -> 按位与操作。

key <<= 2; key |= map[array[i] - 'A']; key &= 0xfffff; 

代码的话，除了求 key 的地方不同，整个框架和解法一也是一样的。

public List<String> findRepeatedDnaSequences(String s) { int len = s.length(); if (len == 0 || len < 10) { return new ArrayList<>(); } Set<String> res = new HashSet<>(); Set<Integer> set = new HashSet<>(); char map[] = new char[26]; map['A' - 'A'] = 0; map['C' - 'A'] = 1; map['G' - 'A'] = 2; map['T' - 'A'] = 3; int key = 0; char[] array = s.toCharArray(); //第一组单独初始化出来 for (int i = 0; i < 10; i++) { key = key << 2 | map[array[i] - 'A']; } set.add(key); for (int i = 10; i < len; i++) { key <<= 2; key |= map[array[i] - 'A']; key &= 0xfffff; if (set.contains(key)) { res.add(s.substring(i - 9, i + 1)); } else { set.add(key); } } return new ArrayList<>(res); } 

至于求 key 的话，我们单独用了一个 map 进行了映射，那么能不能不用 map 呢？可以的，参考 这里。

我们知道每个字母本质上就是一个数字，至于对应关系就是 ASCII 码值。

A -> 65 1000001 C -> 65 1000011 G -> 65 1000111 T -> 65 1010100 

所以每个字母天然的就映射到了一个序列，我们并不需要 map 人为的转换。此时一个字母映射到了 7 个二进制位，但观察上边 4 个数字我们其实只用低三位就可以区分这四个字母了。

A -> 001 C -> 011 G -> 111 T -> 100 

所以对应规则就出来了，相对于之前的改变的地方，此时我们每次需要移 3位，并且按位与的话，因为每个字母对应三位，10 个字母总共需要 30 位，所以我们需要把 key 和111111111111111111111111111111(0x3fffffff) 也就是 30 个 1 进行按位与。

至于把字母转为 key ，我们只需要把低三位和 111 也就是十进制的 7 按位与一下即可。

key <<= 3; key |= (array[i] & 7); key &= 0x3fffffff; 

然后其他的地方，和上边通过 map 得到 key 的解法也没什么区别了。

public List<String> findRepeatedDnaSequences(String s) { int len = s.length(); if (len == 0 || len < 10) { return new ArrayList<>(); } Set<String> res = new HashSet<>(); Set<Integer> set = new HashSet<>(); int key = 0; char[] array = s.toCharArray(); for (int i = 0; i < 10; i++) { key <<= 3; key |= (array[i] & 7); } set.add(key); for (int i = 10; i < len; i++) { key <<= 3; key |= (array[i] & 7); key &= 0x3fffffff; if (set.contains(key)) { res.add(s.substring(i - 9, i + 1)); } else { set.add(key); } } return new ArrayList<>(res); } 

总

解法一的话是很常规的思路。解法二的话，通过对 key 的选取，依次从时间和空间上对解法一进行了轻微的优化，这里需要对二进制有较深的理解。