leetcode中如何查看無重復字符的最長子串

# LeetCode中如何查看無重復字符的最長子串

## 引言

在算法學習和面試準備中，LeetCode是一個不可或缺的平臺。其中，"無重復字符的最長子串"（Longest Substring Without Repeating Characters）是一個經典的字符串處理問題，考察我們對滑動窗口、哈希表等算法的掌握程度。本文將詳細介紹如何在LeetCode上查看、理解并解決這個問題。

## 問題描述

題目編號為[3. 無重復字符的最長子串](https://leetcode.com/problems/longest-substring-without-repeating-characters/)，題目要求：

給定一個字符串 `s`，找出其中不含有重復字符的**最長子串**的長度。

**示例：**

輸入: s = “abcabcbb” 輸出: 3 解釋: 因為無重復字符的最長子串是 “abc”，所以其長度為 3。

## 解題思路

### 1. 暴力法（不推薦）
最直觀的方法是檢查所有可能的子串，判斷是否有重復字符。時間復雜度為O(n3)，效率極低。

```python
def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    res = 0
    for i in range(n):
        for j in range(i, n):
            if len(set(s[i:j+1])) == j - i + 1:
                res = max(res, j - i + 1)
    return res

2. 滑動窗口（推薦）

通過維護一個窗口（用雙指針表示），動態調整窗口大小以排除重復字符。時間復雜度優化至O(n)。

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    res = 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])
        res = max(res, right - left + 1)
    return res

3. 哈希表優化

進一步優化滑動窗口，用哈希表記錄字符的最新位置，直接移動左指針。

def lengthOfLongestSubstring(s: str) -> int:
    char_map = {}
    left = 0
    res = 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
        res = max(res, right - left + 1)
    return res

在LeetCode上查看題目

1. 登錄LeetCode：訪問LeetCode官網并登錄賬號。
2. 搜索題目：在搜索欄輸入“3”或“無重復字符的最長子串”。
3. 題目頁面：
   • 閱讀題目描述和示例。
   • 查看約束條件（如字符串長度限制）。
   • 點擊“Discuss”查看其他用戶的解法。
4. 提交代碼：
   • 選擇編程語言（Python/Java等）。
   • 編寫代碼后點擊“Submit”測試。

代碼詳解（以Python為例）

滑動窗口實現

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，記錄每個字符是否出現過
        occ = set()
        n = len(s)
        # 右指針，初始值為-1，相當于在字符串左側，還未移動
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指針向右移動一格，移除一個字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不斷移動右指針
                occ.add(s[rk + 1])
                rk += 1
            # 第i到rk個字符是一個極長的無重復字符子串
            ans = max(ans, rk - i + 1)
        return ans

復雜度分析

• 時間復雜度：O(n)，每個字符最多被訪問兩次。
• 空間復雜度：O(∣Σ∣)，其中Σ表示字符集的大小。

常見錯誤與調試

1. 邊界條件：空字符串或全重復字符（如”aaaa”）。
2. 指針更新邏輯：左指針移動時需確保不回溯。
3. 哈希表沖突：需檢查字符是否在當前窗口內。

擴展練習

• 至多包含兩個不同字符的最長子串
• 至多包含K個不同字符的最長子串

總結

通過滑動窗口和哈希表，可以高效解決“無重復字符的最長子串”問題。在LeetCode上練習時，建議： 1. 先理解題目和示例； 2. 手寫偽代碼梳理邏輯； 3. 逐步優化解法； 4. 利用討論區學習他人思路。

掌握此類問題后，對處理其他子串或數組問題將大有裨益。

附錄：LeetCode相關題目分類

”`

這篇文章提供了從問題描述到解決方案的完整路徑，并包含代碼示例和LeetCode操作指南，總字數約1350字。