题目描述
请从字符串中找出⼀个最⻓的不包含重复字符的⼦字符串，计算该最⻓⼦字符串的⻓度。
数据范围: ⻓度⼩于40000
示例1
输⼊："abcabcbb"
返回值：3
说明：因为⽆重复字符的最⻓⼦串是"abc"，所以其⻓度为 3。
示例2
输⼊："bbbbb"
返回值：1
说明：因为⽆重复字符的最⻓⼦串是"b"，所以其⻓度为 1
示例3
输⼊："pwwkew"
返回值：3
说明：因为⽆重复字符的最⻓⼦串是 "wke"，所以其⻓度为 3。
思路及解答
暴力枚举
双层循环枚举所有子串，检查是否包含重复字符
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
int n = s.length();
int maxLen = 0;
// 枚举所有可能的子串起始位置
for (int i = 0; i < n; i++) {
// 枚举所有可能的子串结束位置
for (int j = i; j < n; j++) {
// 检查子串s[i..j]是否无重复
if (isUnique(s, i, j)) {
maxLen = Math.max(maxLen, j - i + 1);
} else {
break; // 有重复，内层循环可提前结束
}
}
}
return maxLen;
}
// 检查子串s[left..right]是否无重复字符
private boolean isUnique(String s, int left, int right) {
Set<Character> set = new HashSet<>();
for (int i = left; i <= right; i++) {
char c = s.charAt(i);
if (set.contains(c)) {
return false;
}
set.add(c);
}
return true;
}
}- 时间复杂度：O(n³)，外层循环n次，内层循环最多n次，isUnique检查O(n)
- 空间复杂度：O(min(n,128))，字符集大小有限
滑动窗口（基础版）
右指针扩展窗口，左指针收缩窗口以消除重复
窗口定义：
left：窗口左边界right：窗口右边界window：当前窗口内的字符集合
执行过程示例（"abcabcbb"）：
初始: left=0, right=0, window={}, maxLen=0
1. 添加'a': window={a}, right=1, maxLen=1
2. 添加'b': window={a,b}, right=2, maxLen=2
3. 添加'c': window={a,b,c}, right=3, maxLen=3
4. 添加'a'(重复): 移除s[0]='a', left=1
5. 添加'a': window={b,c,a}, right=4, maxLen=3
...
结果: 3import java.util.HashSet;
import java.util.Set;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
Set<Character> window = new HashSet<>();
int left = 0, right = 0;
int maxLen = 0;
int n = s.length();
while (right < n) {
char c = s.charAt(right);
// 如果当前字符不在窗口中，扩展窗口
if (!window.contains(c)) {
window.add(c);
right++;
maxLen = Math.max(maxLen, right - left);
}
// 如果当前字符已在窗口中，收缩窗口
else {
window.remove(s.charAt(left));
left++;
}
}
return maxLen;
}
}- 时间复杂度：O(2n) = O(n)，每个字符最多被访问两次
- 空间复杂度：O(min(n,128))，字符集大小固定
优化滑动窗口
遇到重复字符时，左指针直接跳转到重复字符的下一个位置
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
Map<Character, Integer> charIndex = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已存在且在当前窗口内
if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
// 左指针直接跳转到重复字符的下一个位置
left = charIndex.get(c) + 1;
}
// 更新字符的最后出现位置
charIndex.put(c, right);
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}- 时间复杂度：O(n)
- 空间复杂度：O(min(n,128))
进一步优化：使用数组替代HashMap
ASCII字符只有128个，可使用固定数组，即使用int[128]记录字符最后出现的位置，-1表示未出现
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
int[] lastIndex = new int[128]; // ASCII字符集
Arrays.fill(lastIndex, -1); // 初始化为-1表示未出现
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符在当前窗口内出现过
if (lastIndex[c] >= left) {
left = lastIndex[c] + 1; // 直接跳转
}
// 更新字符的最后出现位置
lastIndex[c] = right;
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}- 时间复杂度：O(n)
- 空间复杂度：O(1) - 固定128大小