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

题目要求

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

解题思路

这是一道比较典型的滑动窗口的问题。

方法	时间复杂度	空间复杂度
滑动窗口	O(n)	O(1)

滑动窗口

滑动窗口题目的解题思路：

• 定义两个指针，分别指向滑动窗口的左边界和右边界
• 定义一个条件（本题为无重复字符）
• 移动右边界，修改条件
• 判断条件是否成立，如果不成立，移动左边界

滑动窗口伪代码：

    public void lengthOfWindow(String s) {
        // 定义条件
        int 条件;
        // 定义窗口的左边界left
        int left = 0;
        // 定义窗口的右边界i
        for(int i = 0; i < s.length(); i++){
            // 如果不满足条件，移动左边界
            while(left < i && 不满足条件）
                修改条件；
                left++;
            }
            修改条件；
        }
    }

Java代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 用count数组来记录字符出现的次数，长度128
        int[] count = new int[128];
        int res = 0;
        // 定义窗口的左边界left
        int left = 0;
        // 定义窗口的右边界i
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            // 如果有重复的字符，则缩小左边窗口，直到没有重复的字符
            while(left < i && count[c] > 0){
                count[s.charAt(left)]--;
                left++;
            }
            // 走到这里，都是确定没有重复的字符，记录一下长度
            count[c]++;
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}

总结

求最长子串的题目，通常都可以尝试用「滑动窗口」的解法。

滑动窗口有一套自己的模板代码，很多题只是条件在不断变化，整体框架并没有变化。

可以按照模板代码搭出整体的框架，然后填充判断条件的逻辑。

所以滑动窗口的核心在「条件判断」的逻辑，这里通常可以做一些优化，来提高程序运行的效率。

如果用滑动窗口解决问题超时，可以想想怎么优化条件判断的逻辑，将它变成O(1)的时间复杂度。