剑指offer-79、最⻓不含重复字符的
题目描述
请从字符串中找出⼀个最⻓的不包含重复字符的⼦字符串，计算该最⻓⼦字符串的⻓度。
数据范围: ⻓度⼩于40000
示例1
输⼊："abcabcbb"
返回值：3
说明：因为⽆重复字符的最⻓⼦串是"abc"，所以其⻓度为 3。
示例2
输⼊："bbbbb"
返回值：1
说明：因为⽆重复字符的最⻓⼦串是"b"，所以其⻓度为 1
示例3
输⼊："pwwkew"
返回值：3
说明：因为⽆重复字符的最⻓⼦串是 "wke"，所以其⻓度为 3。
思路及解答
暴力枚举
双层循环枚举所有子串，检查是否包含重复字符
java
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"）：
text
初始: 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 ... 结果: 3java
import 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))，字符集大小固定
优化滑动窗口
遇到重复字符时，左指针直接跳转到重复字符的下一个位置
java
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表示未出现
java
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); }