hot100之滑动窗口

无重复字符的最长字串(003)

先看代码

class Solution {
 public int lengthOfLongestSubstring(String s) {
 int res = 0;
 int lef = 0;
 int rig = 0;
 int[] memo = new int[128];
 while (rig < s.length()){
 char clef = s.charAt(lef);
 char crig = s.charAt(rig);
 if (memo[crig] > 0){
 memo[clef]--;
 lef++;
 continue;
 }
 memo[crig]++;
 res = Math.max(res, rig - lef + 1);
 rig++;
 }
 return res;
 }
}

• 分析

根据题目条件<无重复>

通过lef和rig 维护一个滑动窗口, memo来记录遇到字符的次数

rig一直向右扩张, 当出现数字重复, 移动lef 收缩窗口

• 感悟

寻找连续区间就让人很自然而然想到滑动窗口

每次窗口移动只用考虑(入窗口, 出窗口)的元素对窗口整体的影响

找到字符串中所有的字母异位词(438)

先看代码

class Solution {
 public List<Integer> findAnagrams(String s, String p) {
 List<Integer> res = new ArrayList<>();
 int lef = 0;
 int rig = 0;
 int[] memo = new int[26];
 for (char c : p.toCharArray()){
 memo[c - 'a']++;
 }
 while(rig < s.length()){
 int idx = s.charAt(rig) - 'a';
 memo[idx]--;
 while(memo[idx] < 0){
 memo[s.charAt(lef) - 'a']++;
 lef++;
 }
 if (rig - lef + 1 == p.length()) res.add(lef);
 rig++;
 }
 return res;
 }
}

• 分析

和无重复字符的最长字串基本一致, 扩张收缩窗口, 达到条件添加到res

• 感悟

暂无