剑指offer-79、最⻓不含重复字符的

题目描述请从字符串中找出⼀个最⻓的不包含重复字符的⼦字符串计算该最⻓⼦字符串的⻓度。数据范围: ⻓度⼩于40000示例1输⼊abcabcbb返回值3说明因为⽆重复字符的最⻓⼦串是abc所以其⻓度为 3。示例2输⼊bbbbb返回值1说明因为⽆重复字符的最⻓⼦串是b所以其⻓度为 1示例3输⼊pwwkew返回值3说明因为⽆重复字符的最⻓⼦串是 wke所以其⻓度为 3。思路及解答暴力枚举双层循环枚举所有子串检查是否包含重复字符javapublic 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) { SetCharacter 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当前窗口内的字符集合执行过程示例abcabcbbtext初始: left0, right0, window{}, maxLen0 1. 添加a: window{a}, right1, maxLen1 2. 添加b: window{a,b}, right2, maxLen2 3. 添加c: window{a,b,c}, right3, maxLen3 4. 添加a(重复): 移除s[0]a, left1 5. 添加a: window{b,c,a}, right4, maxLen3 ... 结果: 3javaimport java.util.HashSet; import java.util.Set; public class Solution { public int lengthOfLongestSubstring(String s) { if (s null || s.length() 0) return 0; SetCharacter 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))字符集大小固定优化滑动窗口遇到重复字符时左指针直接跳转到重复字符的下一个位置javaimport java.util.HashMap; import java.util.Map; public class Solution { public int lengthOfLongestSubstring(String s) { if (s null || s.length() 0) return 0; MapCharacter, 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))进一步优化使用数组替代HashMapASCII字符只有128个可使用固定数组即使用int[128]记录字符最后出现的位置-1表示未出现javapublic 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); }