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. 找到字符串中所有字母异位词*
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时，移除掉这个word
if (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;
}
}
