LeetCode-Q3-无重复字符的最长子串

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 991 阅读时长 ≈ 2 分钟

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

问题描述

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

  • 示例 1:
1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  • 示例 2:
1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
  • 示例 3:
1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路

  1. 粗暴的方法是列出所有子字符串，再检查这些子字符串是否不重复。时间复杂度是$O(n^3)$，空间复杂度是$O(n)$
  2. 暴力法多做了很多无用的判断，下面我们进行优化，考虑如下的字符串，我们从位置0出发的最长子串是abcd,在位置4遇到了重复字符c,那么下一个可能的最长子串应该是从位置3开始的最长子串。以此类推，这样可以减少很多无用的check。
1
2
|a|b|c|d|c|e|f|e|
|0|1|2|3|4|5|6|7|

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int length =s.length();
        int max = 0; //最大值
        int before =0;
        int subStart = 0; // 子串开始的位置
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0; j < length; j++) {
            if (map.containsKey(s.charAt(j))) { // 已经出现过的字符
                before = map.get(s.charAt(j));
                subStart = Math.max(before,subStart); // 确认是否重复
            }
            max = Math.max(max,j-subStart+1);
            map.put(s.charAt(j), j + 1);
        }
        return max;
    }
}