leetcode—滑动窗口

1 无重复字符的最长子串

给定一个字符串?s?，请你找出其中不含有重复字符的?最长子串?的长度。

示例?1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

方法：

滑动窗口

1. 使用两个指针 表示字符串中某个子串的左右边界【i， right】
2. 在每一步的操作中，将左指针i 向右移动一位，表示开始枚举下一个字符作为起始位置，然后不断的向右移动右指针（right），需要保证两个指针对应的子串中没有重复的字符，移动结束后，【i ， right】则表示当前不包含重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 定义哈希集合 用于记录每个字符是否出现过
        Set<Character> hs = new HashSet<>();
        // 得到字符串的长度
        int n = s.length();

        // 定义右指针 初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int right = -1;
        int ans = 0;    // 用于记录连续子串的长度

        for(int i = 0; i < n; i++){
            if(i != 0){
                // 左指针向右移动一格，移除一个字符
                hs.remove(s.charAt(i-1));
            }
            while(right + 1 < n && !hs.contains(s.charAt(right + 1))){
                // 将right+1添加到哈希集合中，不断的向右移动指针
                hs.add(s.charAt(right + 1));
                right++;
            }
            // 第i到right个字符是一个极长的无重复字符子串 +1的原因为下标从0开始
            ans = Math.max(ans,right - i + 1);
        }
        return ans;
    }
}

总结：

滑动窗口的逻辑

具体来说就是维护一个窗口，不断滑动，然后更新答案

主要代码如下：

    int left = 0;
    int right = 0;
    while(right < s.zize()){
        // 增大窗口
        windows.add(s[right]);
        right++;
        
        while (window needs shrink){
            // 缩小窗口
            windows.remove(s[left]);
            left++;
        }
    }