Q3.无重复字符的最长子串
问题描述
给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
- 示例 1:
1 | 输入: "abcabcbb" |
- 示例 2:
1 | 输入: "bbbbb" |
- 示例 3:
1 | 输入: "pwwkew" |
思路
- 粗暴的方法是列出所有子字符串,再检查这些子字符串是否不重复。时间复杂度是$O(n^3)$,空间复杂度是$O(n)$
- 暴力法多做了很多无用的判断,下面我们进行优化,考虑如下的字符串,我们从位置0出发的最长子串是abcd,在位置4遇到了重复字符c,那么下一个可能的最长子串应该是从位置3开始的最长子串。以此类推,这样可以减少很多无用的check。
1 | |a|b|c|d|c|e|f|e| |
代码
1 | public class LongestSubstring { |