題目描述

請從字符串中找出⼀個最⻓的不包含重複字符的⼦字符串，計算該最⻓⼦字符串的⻓度。

數據範圍: ⻓度⼩於40000

示例1
輸⼊："abcabcbb"
返回值：3
説明：因為⽆重複字符的最⻓⼦串是"abc"，所以其⻓度為 3。

示例2
輸⼊："bbbbb"
返回值：1
説明：因為⽆重複字符的最⻓⼦串是"b"，所以其⻓度為 1

示例3
輸⼊："pwwkew"
返回值：3
説明：因為⽆重複字符的最⻓⼦串是 "wke"，所以其⻓度為 3。

思路及解答

暴力枚舉

雙層循環枚舉所有子串，檢查是否包含重複字符

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        
        int n = s.length();
        int maxLen = 0;
        
        // 枚舉所有可能的子串起始位置
        for (int i = 0; i < n; i++) {
            // 枚舉所有可能的子串結束位置
            for (int j = i; j < n; j++) {
                // 檢查子串s[i..j]是否無重複
                if (isUnique(s, i, j)) {
                    maxLen = Math.max(maxLen, j - i + 1);
                } else {
                    break; // 有重複，內層循環可提前結束
                }
            }
        }
        
        return maxLen;
    }
    
    // 檢查子串s[left..right]是否無重複字符
    private boolean isUnique(String s, int left, int right) {
        Set<Character> set = new HashSet<>();
        for (int i = left; i <= right; i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                return false;
            }
            set.add(c);
        }
        return true;
    }
}

• 時間複雜度：O(n³)，外層循環n次，內層循環最多n次，isUnique檢查O(n)
• 空間複雜度：O(min(n,128))，字符集大小有限

滑動窗口（基礎版）

右指針擴展窗口，左指針收縮窗口以消除重複

窗口定義：

• left：窗口左邊界
• right：窗口右邊界
• window：當前窗口內的字符集合

執行過程示例（"abcabcbb"）：

初始: left=0, right=0, window={}, maxLen=0
1. 添加'a': window={a}, right=1, maxLen=1
2. 添加'b': window={a,b}, right=2, maxLen=2
3. 添加'c': window={a,b,c}, right=3, maxLen=3
4. 添加'a'(重複): 移除s[0]='a', left=1
5. 添加'a': window={b,c,a}, right=4, maxLen=3
...
結果: 3

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        
        Set<Character> window = new HashSet<>();
        int left = 0, right = 0;
        int maxLen = 0;
        int n = s.length();
        
        while (right < n) {
            char c = s.charAt(right);
            
            // 如果當前字符不在窗口中，擴展窗口
            if (!window.contains(c)) {
                window.add(c);
                right++;
                maxLen = Math.max(maxLen, right - left);
            } 
            // 如果當前字符已在窗口中，收縮窗口
            else {
                window.remove(s.charAt(left));
                left++;
            }
        }
        
        return maxLen;
    }
}

• 時間複雜度：O(2n) = O(n)，每個字符最多被訪問兩次
• 空間複雜度：O(min(n,128))，字符集大小固定

優化滑動窗口

遇到重複字符時，左指針直接跳轉到重複字符的下一個位置

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        
        Map<Character, Integer> charIndex = new HashMap<>();
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            
            // 如果字符已存在且在當前窗口內
            if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
                // 左指針直接跳轉到重複字符的下一個位置
                left = charIndex.get(c) + 1;
            }
            
            // 更新字符的最後出現位置
            charIndex.put(c, right);
            
            // 更新最大長度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

• 時間複雜度：O(n)
• 空間複雜度：O(min(n,128))

進一步優化：使用數組替代HashMap

ASCII字符只有128個，可使用固定數組，即使用int[128]記錄字符最後出現的位置，-1表示未出現

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        
        int[] lastIndex = new int[128]; // ASCII字符集
        Arrays.fill(lastIndex, -1);    // 初始化為-1表示未出現
        
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            
            // 如果字符在當前窗口內出現過
            if (lastIndex[c] >= left) {
                left = lastIndex[c] + 1; // 直接跳轉
            }
            
            // 更新字符的最後出現位置
            lastIndex[c] = right;
            
            // 更新最大長度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

• 時間複雜度：O(n)
• 空間複雜度：O(1) - 固定128大小