# LeetCode中怎么找出字符串中無重復最長子串
## 問題描述
在LeetCode題庫中，第3題"無重復字符的最長子串"（Longest Substring Without Repeating Characters）是一個經典的字符串處理問題。題目要求：
給定一個字符串 `s`，找出其中不含有重復字符的**最長子串**的長度。
**示例：**
輸入: s = “abcabcbb” 輸出: 3 解釋: 因為無重復字符的最長子串是 “abc”，所以其長度為 3。
## 問題分析
### 關鍵概念
1. **子串**：字符串中連續的字符序列
2. **無重復字符**：子串中所有字符都是唯一的
3. **最長**：在所有符合條件的子串中長度最大的
### 難點分析
- 需要高效地檢查字符是否重復
- 需要跟蹤當前無重復子串的起始位置
- 需要在遍歷過程中動態更新最大長度
## 解決方案
### 方法一：暴力解法（不推薦）
#### 思路
檢查所有可能的子串，判斷是否有重復字符，記錄最長長度。
```python
def lengthOfLongestSubstring(s: str) -> int:
n = len(s)
max_len = 0
for i in range(n):
for j in range(i, n):
if len(set(s[i:j+1])) == j-i+1:
max_len = max(max_len, j-i+1)
return max_len
維護一個滑動窗口，窗口內的字符都是唯一的。通過移動窗口的左右邊界來尋找最長子串。
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
記錄字符及其索引，遇到重復字符時直接跳轉左指針。
def lengthOfLongestSubstring(s: str) -> int:
char_map = {}
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in char_map:
left = max(left, char_map[s[right]] + 1)
char_map[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
| 方法 | 時間復雜度 | 空間復雜度 | LeetCode執行用時 |
|---|---|---|---|
| 暴力法 | O(n3) | O(min(m,n)) | >1000ms |
| 滑動窗口 | O(n) | O(min(m,n)) | ~100ms |
| 優化滑動窗口 | O(n) | O(min(m,n)) | ~50ms |
"" → 返回0"bbbbb" → 返回1"abcdef" → 返回字符串長度"pwwkew" → 返回3（”wke”）assert lengthOfLongestSubstring("") == 0
assert lengthOfLongestSubstring("bbbbb") == 1
assert lengthOfLongestSubstring("abcabcbb") == 3
assert lengthOfLongestSubstring("pwwkew") == 3
def lengthOfLongestSubstring(s: str) -> int:
# 假設字符串只包含擴展ASCII字符（256個）
char_index = [-1] * 256
left = 0
max_len = 0
for right in range(len(s)):
if char_index[ord(s[right])] >= left:
left = char_index[ord(s[right])] + 1
char_index[ord(s[right])] = right
max_len = max(max_len, right - left + 1)
return max_len
對于已知字符范圍的情況（如小寫字母），可以進一步減少空間使用：
char_index = [-1] * 26 # 僅小寫字母
# 錯誤示范：未正確處理左指針移動
def lengthOfLongestSubstring(s: str) -> int:
char_map = {}
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in char_map:
left = char_map[s[right]] # 錯誤：應該+1
char_map[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
解決”無重復字符的最長子串”問題的關鍵在于： 1. 理解滑動窗口的概念 2. 選擇合適的哈希結構存儲字符位置 3. 正確處理指針移動和邊界條件
優化后的滑動窗口算法是最優解，時間復雜度O(n)，空間復雜度O(min(m,n))。建議通過反復練習掌握滑動窗口的常見模式，這對解決類似問題大有裨益。
通過系統學習和實踐，你不僅能夠解決這個問題，還能掌握一類字符串處理問題的通用解法。 “`
這篇文章共計約2200字，涵蓋了問題描述、多種解法、復雜度分析、邊界處理、優化技巧、實際應用和學習建議等內容，采用Markdown格式編寫，適合技術博客或學習筆記。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
