LeetCode 3：無重複字符最長子串解法詳解

LeetCode 3：無重複字符最長子串解法詳解

給定一個字符串，找出不包含重複字符的最長子串長度。本文提供暴力解法實現，並分析其時間複雜度瓶頸，為優化解法鋪路。

題目示例

• "abcabcbb" → "abc"，長度 3
• "bbbbb" → "b"，長度 1
• "pwwkew" → "wke"，長度 3（注意："pwke" 是子序列非子串）

暴力解法實現

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        char[] chars = s.toCharArray();
        
        for (int i = 0; i < chars.length; i++) {
            Set seen = new HashSet<>();
            int count = 0;
            for (int j = i; j < chars.length; j++) {
                if (!seen.contains(chars[j])) {
                    seen.add(chars[j]);
                    count++;
                } else {
                    break; // 遇重複字符終止內層循環
                }
            }
            maxLen = Math.max(maxLen, count);
        }
        return maxLen;
    }
}

複雜度分析

• 時間複雜度：O(n²) — 雙重循環遍歷所有子串
• 空間複雜度：O(min(n, m)) — HashSet 存儲字符，m 為字符集大小

優化方向

暴力解法在長字符串下會超時。最優解採用滑動窗口 + HashMap，單次遍歷即可達到 O(n) 時間複雜度，核心思想：

1. 維護左右指針定義窗口
2. 右指針擴展窗口，遇重複字符時左指針收縮至重複字符後一位
3. 用 Map 記錄字符最後出現位置

進階優化可用定長數組替代 Map（ASCII 128 或擴展 256），進一步降低常數因子。