算法练习03——滑动窗口

3. 无重复字符的最长子串*

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

class Solution {public int lengthOfLongestSubstring(String s) {//哈希表＋滑动窗口int res=0;int left=-1;Map<Character,Integer> hash=new HashMap<>();for(int right=0;right<s.length();right++){if(hash.containsKey(s.charAt(right))){left=Math.max(left,hash.get(s.charAt(right)));}hash.put(s.charAt(right),right);res=Math.max(res,right-left);}return res;}
}

438. 找到字符串中所有字母异位词*

https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> res=new ArrayList<>();int sLen=s.length();int pLen=p.length();if(sLen<pLen){return res;}//建立两个数组存放字符串中字母出现的词频，并以此作为标准比较int [] scount=new int[26];int [] pcount=new int[26];//当滑动窗口的首位在s[0]处时 （相当于放置滑动窗口进入数组）for(int i=0;i<pLen;i++){++scount[s.charAt(i)-'a']; //记录s中前pLen个字母的词频++pcount[p.charAt(i)-'a']; //记录要寻找的字符串中每个字母的词频(只用进行一次来确定)}//判断放置处是否有异位词  (在放置时只需判断一次)if(Arrays.equals(scount,pcount)){res.add(0);}   //开始让窗口进行滑动for(int i=0;i<sLen-pLen;i++){ //i是滑动前的首位--scount[s.charAt(i) -'a'];       //将滑动前首位的词频删去++scount[s.charAt(i+pLen) -'a'];  //增加滑动后最后一位的词频（以此达到滑动的效果）//判断滑动后处，是否有异位词if(Arrays.equals(scount,pcount)){res.add(i+1);} }return res;}
}

30. 串联所有单词的子串***(hard)

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> res = new ArrayList<>();// 所有单词的个数int num = words.length;// 每个单词的长度（是相同的）int wordLen = words[0].length();// 字符串长度int stringLen = s.length();for (int i = 0; i < wordLen; i++) {// 遍历的长度超过了整个字符串的长度，退出循环if (i + num * wordLen > stringLen) {break;}// differ表示窗口中的单词频次和words中的单词频次之差Map<String, Integer> differ = new HashMap<>();// 初始化窗口，窗口长度为num * wordLen,依次计算窗口里每个切分的单词的频次for (int j = 0; j < num; j++) {String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);differ.put(word, differ.getOrDefault(word, 0) + 1);}// 遍历words中的word，对窗口里每个单词计算差值for (String word : words) {differ.put(word, differ.getOrDefault(word, 0) - 1);// 差值为0时，移除掉这个wordif (differ.get(word) == 0) {differ.remove(word);}}// 开始滑动窗口for (int start = i; start < stringLen - num * wordLen + 1; start += wordLen) {if (start != i) {// 右边的单词滑进来String word = s.substring(start + (num - 1) * wordLen, start + num * wordLen);differ.put(word, differ.getOrDefault(word, 0) + 1);if (differ.get(word) == 0) {differ.remove(word);}// 左边的单词滑出去word = s.substring(start - wordLen, start);differ.put(word, differ.getOrDefault(word, 0) - 1);if (differ.get(word) == 0) {differ.remove(word);}word = s.substring(start - wordLen, start);}// 窗口匹配的单词数等于words中对应的单词数if (differ.isEmpty()) {res.add(start);}}}return res;}
}