【LC100】No3. 无重复字符的最长子串

题目描述

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

提示:

• 0 <= s.length <= 5 * 104

• s 由英文字母、数字、符号和空格组成

示例

示例 1:

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

示例 2:

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

示例 3:

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

链接

思路

本来是做出来的，结果陷在空格难以判断的泥潭中，心好累。

解法一：暴力法

简单粗暴的正向遍历，枚举所有子串，逐一判断是否有重复字符。

使用哈希表降低时间复杂度。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int res = 0; 
        for (int i = 0; i < n; i++) {
            Set<Character> set = new HashSet<>(); 
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (set.contains(c)) {
                    break;
                }
                set.add(c);
                res = Math.max(j - i + 1, res);
            }
        }
        return res;
    }
}

• 时间复杂度：O(n²)

• 空间复杂度：O(n²)

解法二：滑动窗口

想不出来的方法。

相向双指针，左右指针共同维护一个滑动窗口。

优点在于，保证了窗口内的字符串是必定符合题意的。

当窗口移动时，右指针遇到重复的字母时，就右移左指针缩小窗口，直到找到符合题意的窗口。

也即，窗口是从“不满足题目要求”到“满足题目要求”，反之也可以，这类题目都可以使用滑动窗口来做。

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int res = 0;
        // 左右指针维护一个滑动窗口
        int left = 0;
        // 记录字符的出现次数
        int[] charNums = new int[128];
        for (int right = 0; right < chars.length; right++) {
            charNums[chars[right]]++;
            // 出现了重复字符，窗口左指针右移，相当于是左指针指向的字符出现次数-1
            while (charNums[chars[right]] > 1) {
                charNums[chars[left]]--;
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)，ASCII字符最多128个。