hot100之滑动窗口

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

先看代码

1. class Solution {
2.     public int lengthOfLongestSubstring(String s) {
3.         int res = 0;
4.         int lef = 0;
5.         int rig = 0;
6.         int[] memo = new int[128];
8.         while (rig < s.length()){
9.             char clef = s.charAt(lef);
10.             char crig = s.charAt(rig);
11.             if (memo[crig] > 0){
12.                 memo[clef]--;
13.                 lef++;
14.                 continue;
15.             }
16.             memo[crig]++;
17.             res = Math.max(res, rig - lef + 1);
18.             rig++;
19.         }
20.         return res;
21.     }
22. }

复制代码

• 分析
  

根据题目条件
通过lef和rig 维护一个滑动窗口, memo来记载遇到字符的次数
rig不停向右扩张, 当出现数字重复, 移动lef 收缩窗口

• 感悟
  

寻找连续区间就让人很自然而然想到滑动窗口
每次窗口移动只用考虑(入窗口, 出窗口)的元素对窗口整体的影响
找到字符串中所有的字母异位词(438)

先看代码

1. class Solution {
2.     public List<Integer> findAnagrams(String s, String p) {
3.         List<Integer> res = new ArrayList<>();
4.         int lef = 0;
5.         int rig = 0;
6.         int[] memo = new int[26];
7.         for (char c : p.toCharArray()){
8.             memo[c - 'a']++;
9.         }
10.         while(rig < s.length()){
11.             int idx = s.charAt(rig) - 'a';
12.             memo[idx]--;
13.             while(memo[idx] < 0){
14.                 memo[s.charAt(lef) - 'a']++;
15.                 lef++;
16.             }
17.             if (rig - lef + 1 == p.length()) res.add(lef);
18.             rig++;
19.         }
20.         return res;
21.     }
22. }

复制代码

• 分析
  

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

• 感悟
  

暂无