算法题：无重复字符的最长子串

编码如写诗

发布于 2026-03-02 20:49:06

300

文章被收录于专栏：编码如写诗编码如写诗

算法题：无重复字符的最长子串

聊聊技术。

今天刷到道挺有意思的题，无重复字符的最长子串，LeetCode第3题。

题目是这样的：给你一个字符串，找到其中不含有重复字符的最长子串的长度。

题目理解

举个栗子，字符串是"abcabcbb"。

不重复字符的最长子串是"abc"，长度是3。

如果是"bbbbb"，最长的子串是"b"，长度是1。

如果是"pwwkew"，最长的子串是"wke"，长度是3。

注意是子串，不是子序列，字符必须是连续的。

思路分析

最暴力的解法是枚举所有子串，然后用哈希表检查有没有重复字符。

这个思路听着简单，但时间复杂度是O(n³)，太慢了。

稍微聪明点的方法是用滑动窗口+哈希表。

维护一个窗口，窗口里是没有重复字符的子串。

用哈希表记录每个字符最后出现的位置。

如果当前字符已经在窗口里出现过，就把窗口左边移到这个字符上次出现的位置的右边。

然后更新最长长度。

这个方法叫双指针，时间复杂度是O(n)。

复杂度分析

滑动窗口法：

时间复杂度：O(n)，n是字符串长度
空间复杂度：O(min(m, n))，m是字符集大小，n是字符串长度

代码实现

package main

import "fmt"

// 滑动窗口法
func lengthOfLongestSubstring(s string) int {
 if len(s) == 0 {
  return 0
 }

 charIndex := make(map[rune]int)
 maxLen := 0
 left := 0

 for right, char := range s {
  // 如果字符在窗口里出现过，移动左边边界
  if lastIndex, ok := charIndex[char]; ok && lastIndex >= left {
   left = lastIndex + 1
  }

  // 更新最长长度
  if right-left+1 > maxLen {
   maxLen = right - left + 1
  }

  // 记录字符的位置
  charIndex[char] = right
 }

 return maxLen
}

// 暴力法（仅作对比）
func lengthOfLongestSubstringBruteForce(s string) int {
 n := len(s)
 maxLen := 0

 for i := 0; i < n; i++ {
  charSet := make(map[byte]bool)
  for j := i; j < n; j++ {
   if charSet[s[j]] {
    break
   }
   charSet[s[j]] = true
   if j-i+1 > maxLen {
    maxLen = j - i + 1
   }
  }
 }

 return maxLen
}

func main() {
 // 测试用例
 s1 := "abcabcbb"
 fmt.Printf("输入: %s, 最长子串长度: %d\n", s1, lengthOfLongestSubstring(s1))

 s2 := "bbbbb"
 fmt.Printf("输入: %s, 最长子串长度: %d\n", s2, lengthOfLongestSubstring(s2))

 s3 := "pwwkew"
 fmt.Printf("输入: %s, 最长子串长度: %d\n", s3, lengthOfLongestSubstring(s3))

 s4 := ""
 fmt.Printf("输入: %s, 最长子串长度: %d\n", s4, lengthOfLongestSubstring(s4))

 s5 := "dvdf"
 fmt.Printf("输入: %s, 最长子串长度: %d\n", s5, lengthOfLongestSubstring(s5))

 // 对比暴力法
 fmt.Println("\n对比暴力法:")
 fmt.Printf("输入: %s, 滑动窗口: %d, 暴力法: %d\n", s1, lengthOfLongestSubstring(s1), lengthOfLongestSubstringBruteForce(s1))
 fmt.Printf("输入: %s, 滑动窗口: %d, 暴力法: %d\n", s2, lengthOfLongestSubstring(s2), lengthOfLongestSubstringBruteForce(s2))
}