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

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;
}
}
-------------本文结束感谢您的阅读-------------
坚持分享,您的支持将鼓励我继续创作!
0%