leetcode—滑动窗口-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode—滑动窗口。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1 无重复字符的最长子串

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

示例 1:

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

方法：

滑动窗口

使用两个指针表示字符串中某个子串的左右边界【i， right】
在每一步的操作中，将左指针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;
    }
}

总结：

滑动窗口的逻辑

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

主要代码如下：文章来源地址https://www.toymoban.com/news/detail-798660.html

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

到了这里，关于leetcode—滑动窗口的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！