题目主要信息

所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的，例如 'ACTGGGC' 。

请你实现一个函数找出所有的目标子串，目标连续子串的定义是，长度等于 10 ，且在 DNA 序列中出现次数超过 1 次的连续子串（允许两个连续子串有重合的部分，如下面的示例2所示）。

（注：返回的所有目标子串的顺序必须与原DNA序列的顺序一致，如下面的示例1所示）

方法一：直接求解

具体方法

用一个ArrayList存子串，截取长度为10的子串，遍历所有的可能子串，如果未出现过，并且在后面的序列还会出现，则加入到ArrayList中。最后返回结果。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串一维数组
     */
    public String[] repeatedDNA (String DNA) {
        // write code here
         int len = DNA.length();
        //list，用于存储目标子串
        ArrayList<String> list = new ArrayList<>();
        //新建set，用于去重
        Set<String> set = new HashSet<>();
        for(int i=0;i < len-9;i++){
            //长度为10的子串
            String cur=DNA.substring(i,i+10);
            //未出现过，且在后面的序列会出现，加入到list
            if(!set.contains(cur) && DNA.substring(i+1).indexOf(cur)!=-1){
                list.add(cur);
                set.add(cur);
            }
        }
        //转化为字符串数组
        return list.toArray(new String[list.size()]);
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}{n}^2\mathrm{）}O（n^2）$,遍历的过程中需要判断是否存在重复的子串，函数indexOf函数的时间复杂度为$O(n)O(n)$
• 空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，存结果的ArrayList

方法二：使用哈希表

具体方法

遍历两次字符串，第一次统计 s所有长度为 10的子串的出现次数。

第二次统计出现次数大于1的子串，并存入结果集中，最后返回。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串一维数组
     */
    public String[] repeatedDNA (String DNA) {
        // write code here
        List<String> ans = new ArrayList<>();
        int n = DNA.length();
        Map<String, Integer> map = new HashMap<>();
        // 统计每个长度为10的子串出现的次数
        for(int i=0;i<=n-10;i++){
           String s = DNA.substring(i,i+10);
            map.put(s,map.getOrDefault(s,0)+1);
        }
        // 再次遍历
        for (int i = 0; i + 10 <= n; i++) {
            String cur = DNA.substring(i, i + 10);
            int cnt = map.getOrDefault(cur, 0);
            //遇到出现次数大于1的片段，将其加入输出
            if (cnt >1) 
            {
                ans.add(cur);
                // 删除，防止后面在加入一次
              map.remove(cur);
            }
        }
        return ans.toArray(new String[ans.size()]);
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，遍历两次，但都是一层循环
• 空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，哈希表的长度。