Day 17
题目描述
思路
利用滑动窗口的思想：
- 定义一个hashmap用来存放出现过的字符和它的位置
- 初始在map中存放序号为0的元素和0，beg设置为0
- 从序号1开始向前遍历，判断该元素是否在map中存在
- 如果存在，说明这个元素已经重复，那么将下一个遍历起点变成该字符上一次出现的位置加1为新起点x，更改临时长度len，从之前起点到新起点之间的map依次删除（beg‘到x），将当前元素加入map，将beg设置为x
- 如果不存在，将该元素入队，len++。
- 循环的最后判断len是否大于max，大于就更新max
- 返回max
例子
“abcabcbb”
到第二个a的时候
map
a 0
b 1
c 2
此时len=3
到a时重复
map
a 3
len变为1
max=3
此时的beg变为3了
class Solution {public int lengthOfLongestSubstring(String s) {int beg,len,max,x;max=1;len=1;if(s.length()==0){//处理特殊情况return 0;}Map<Character,Integer> map = new HashMap<>();beg=0;map.put(s.charAt(0),beg);//初始设置值for (int i = 1; i < s.length(); i++) {if (map.containsKey(s.charAt(i))) {//出现重复x=map.get(s.charAt(i))+1;//获取新的起点len=len-(x-beg)+1;//计算新起点的len值for(int j=beg;j<x;j++){//删除旧起点到新起点之间的map值map.remove(s.charAt(j));}map.put(s.charAt(i),i);//加入mapbeg=x;//更新起点}else{map.put(s.charAt(i),i);len++;}if(len>max){max=len;}}return max;}
}
题目描述（抽象题）(官方题解没看懂 过段时间再更新)
思路
初次做法：见代码
class Solution {public HashMap<String,Integer> back(String[] words){//初始化map 因为多次使用 直接使用函数HashMap<String,Integer> map = new HashMap<>();for (int i = 0; i < words.length; i++) {if (map.containsKey(words[i])) {//出现重复的word直接在原先基础上加1map.put(words[i], map.get(words[i]) + 1);}else{map.put(words[i], 1);}}return map;}public List<Integer> findSubstring(String s, String[] words) {ArrayList<Integer> res = new ArrayList<>();//结果集合HashMap<String, Integer> map = new HashMap<>();map=back(words);if(map.get(words[0])==words.length){//如果单词数组中所有单词都是同一个String q="";for(int i=0;i<words.length;i++){q=q+words[i];}map.put(q,1);if(q.length()==s.length()){res.add(0);return res;}else if(q.length()>s.length()){return res;}else{StringBuilder sb = new StringBuilder();for(int i=0;i<=s.length()-q.length();i++){int beg=i;for(int j=i;j<i+q.length();j++){sb.append(s.charAt(j));}if(map.containsKey(sb.toString())){res.add(beg);}sb.delete(0,q.length());}return res;}}int beg=0,len=0,sum=0,m,n,qi;//sum存放符合字串的个数n=words.length;//存放单词数组的长度qi=0;//新起点m=words[0].length();//因为单词长度一样，就统一存放StringBuilder strings = new StringBuilder();//方便拼接字符变成字符串for (int i = 0; i < s.length(); i++) {if(sum==n){//如果每个word都在子串中res.add(beg);//记录起始点sum=0;//清空map=back(words);//重置mapi=qi;//将i换为新的起点continue;//跳出这个循环}strings.append(s.charAt(i));//如果sum不等于word数组的长度，将该字符加入for (int j = i+1; j < i+m; j++) {//因为每个单词长度相同，从这个字符向后添加，直到长度和word一样长if (j>=s.length()){//越界直接返回return res;}strings.append(s.charAt(j));}String res1 = strings.toString();//拼接成字符串if (map.containsKey(res1)&&map.get(res1)>0) {//如果这个字串存在于word数组中//>0的判断是因为word中有些单词不止一个map.put(res1, map.get(res1)-1);//将map中该word数值减一if(sum==0){//说明这是匹配的第一个，要记录begqi=i;//方便如果出现重复，回到qi+1接着遍历beg=i;//记录begsum++;strings.delete(0,strings.length());//清空字符串}else{sum++;strings.delete(0,strings.length());}i=i+m-1;//因为我们是直接遍历从i到i+m-1的所有元素，下次i自动加1，就从i+m遍历}else{//要么就是出现重复或者不存在于word中if(sum==0){//之前没有匹配的strings.delete(0,strings.length());}else{//之前存在匹配的sum=0;//清空i=qi;strings.delete(0,strings.length());map=back(words);}}}if (sum==n){//因为我们是循环开始判断的，可能最后一个子串也满足，特殊处理一下res.add(beg);}return res;}
}
问题：
时间复杂度很高
