题目描述

请从字符串中找出⼀个最⻓的不包含重复字符的⼦字符串，计算该最⻓⼦字符串的⻓度。

数据范围: ⻓度⼩于40000

示例1 输⼊：“abcabcbb” 返回值：3 说明：因为⽆重复字符的最⻓⼦串是"abc"，所以其⻓度为 3。

示例2 输⼊：“bbbbb” 返回值：1 说明：因为⽆重复字符的最⻓⼦串是"b"，所以其⻓度为 1

示例3 输⼊：“pwwkew” 返回值：3 说明：因为⽆重复字符的最⻓⼦串是 “wke”，所以其⻓度为 3。

思路及解答

暴力枚举

双层循环枚举所有子串，检查是否包含重复字符

  • 时间复杂度：O(n³)，外层循环n次，内层循环最多n次，isUnique检查O(n)

  • 空间复杂度：O(min(n,128))，字符集大小有限

滑动窗口（基础版）

右指针扩展窗口，左指针收缩窗口以消除重复

窗口定义：

  • left：窗口左边界

  • right：窗口右边界

  • window：当前窗口内的字符集合

执行过程示例（“abcabcbb”）：

  • 时间复杂度：O(2n) = O(n)，每个字符最多被访问两次

  • 空间复杂度：O(min(n,128))，字符集大小固定

优化滑动窗口

遇到重复字符时，左指针直接跳转到重复字符的下一个位置

  • 时间复杂度：O(n)

  • 空间复杂度：O(min(n,128))

进一步优化：使用数组替代HashMap

ASCII字符只有128个，可使用固定数组，即使用int[128]记录字符最后出现的位置，-1表示未出现

  • 时间复杂度：O(n)

  • 空间复杂度：O(1) - 固定128大小