hot100-一刷-03滑动窗口(共2道题)

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

题目链接

题目描述

代码实现

分析：因为是要连续的序列，使用滑动窗口 + Set集合来判断即将要加入窗口右端的元素是已经在窗口中出现过。

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;

        // Set去重
        Set<Character> set = new HashSet<>();
        // 滑动窗口
        char[] chars = s.toCharArray();

        int left = 0;
        int right = 0;

        for (; right < s.length(); right++){
            // left < right 也可以不加。 最坏的情况，是left在right前一位
            // 相当于先把该元素移出set， while外又加进set，并且此时left=right， for里right再++
            while(left < right && set.contains(chars[right])){
                set.remove(chars[left]);
                left++;
            }
            set.add(chars[right]);
            // 更新每一轮添加元素时的最大子串长度
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

模板

题解区有人提到滑动窗口的模板题，

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}
// ----------------------------------------
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口
        char[] ss = s.toCharArray();
        Set<Character> set = new HashSet<>();//去重
        int res = 0;//结果
        for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个。
            char ch = ss[right];//right指向的元素，也是当前要考虑的元素
            while(set.contains(ch)) {//set中有ch，则缩短左边界，同时从set集合出元素
                set.remove(ss[left]);
                left++;
            }
            set.add(ss[right]);//别忘。将当前元素加入。
            res = Math.max(res, right - left + 1);//计算当前不重复子串的长度。
        }
        return res;
    }
}

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

题目链接

题目描述

代码实现

分析：
初始化时维护一个pLen大小的窗口，使用数组来记录字母出现的次数。
代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // s 长度小于 p 必然不行
        if(s.length() < p.length()) return new ArrayList<>();
        
        List<Integer> ans = new ArrayList<>();
        int[] arrS = new int[26];
        int[] arrP = new int[26];
    
        // 初始化时维护一个pLen大小的窗口
        for(int i = 0; i < p.length(); i++){
            // 记录p里所有字母出现的次数
            arrP[p.charAt(i) - 'a']++;
            arrS[s.charAt(i) - 'a']++;
        }
        if(Arrays.equals(arrP,arrS)){
            ans.add(0);
        }

        for(int i = 0; i < s.length() - p.length(); i++){
            // 头出
            arrS[s.charAt(i) - 'a']--;
            // 尾进
            arrS[s.charAt(i + p.length()) - 'a']++;
            // 新头满足则添加到ans，不满足就再判断下一轮
            if(Arrays.equals(arrP,arrS)){
                ans.add(i+1);
            }
        }
        return ans;
    }
}