使用哈希表實現LeetCode 438（找到字符串中所有字母異位詞）的滑動窗口算法，適用於字符串包含任意字符（不僅限於小寫字母）的場景。核心思路是通過哈希表記錄字符頻率，結合固定大小的滑動窗口判斷子串是否為異位詞。

實現代碼

import java.util.*;

public class FindAnagramsWithHash {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int sLen = s.length();
        int pLen = p.length();

        // 邊界條件：若s長度小於p，直接返回空列表
        if (sLen < pLen) {
            return result;
        }

        // 哈希表存儲p中每個字符的頻率
        Map<Character, Integer> pFreq = new HashMap<>();
        // 哈希表存儲當前滑動窗口中每個字符的頻率
        Map<Character, Integer> windowFreq = new HashMap<>();

        // 初始化p的頻率表
        for (char c : p.toCharArray()) {
            pFreq.put(c, pFreq.getOrDefault(c, 0) + 1);
        }

        // 初始化滑動窗口的初始狀態（前pLen個字符）
        for (int i = 0; i < pLen; i++) {
            char c = s.charAt(i);
            windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);
        }

        // 檢查初始窗口是否為p的異位詞
        if (isFreqEqual(pFreq, windowFreq)) {
            result.add(0);
        }

        // 滑動窗口：從pLen位置開始向右移動
        for (int right = pLen; right < sLen; right++) {
            // 1. 加入右側新字符（擴展窗口右邊界）
            char newChar = s.charAt(right);
            windowFreq.put(newChar, windowFreq.getOrDefault(newChar, 0) + 1);

            // 2. 移除左側溢出字符（收縮窗口左邊界，保持窗口大小為pLen）
            char leftChar = s.charAt(right - pLen);
            int count = windowFreq.get(leftChar);
            if (count == 1) {
                windowFreq.remove(leftChar); // 頻率為1時，移除後頻率為0，直接刪除鍵
            } else {
                windowFreq.put(leftChar, count - 1); // 頻率減1
            }

            // 3. 檢查當前窗口是否與p的頻率匹配
            if (isFreqEqual(pFreq, windowFreq)) {
                // 當前窗口的起始索引 = right - pLen + 1
                result.add(right - pLen + 1);
            }
        }

        return result;
    }

    // 輔助函數：判斷兩個頻率哈希表是否完全相等
    private boolean isFreqEqual(Map<Character, Integer> map1, Map<Character, Integer> map2) {
        // 若鍵的數量不同，直接不匹配
        if (map1.size() != map2.size()) {
            return false;
        }
        // 逐個檢查鍵對應的頻率是否相同
        for (char c : map1.keySet()) {
            // 若map2中沒有該鍵，或頻率不同，則不匹配
            if (!map2.containsKey(c) || !map1.get(c).equals(map2.get(c))) {
                return false;
            }
        }
        return true;
    }
}

關鍵思路解析

  1. 哈希表的作用：
  • pFreq 存儲字符串 p 中每個字符的出現次數（頻率）。
  • windowFreq 存儲當前滑動窗口（長度為 pLen）中每個字符的頻率。
  1. 滑動窗口邏輯：
  • 窗口大小固定為 pLen（異位詞長度必與 p 相同）。
  • 右指針 right 從 pLen 開始移動，每次移動時：
  • 加入右側新字符 s[right]，更新 windowFreq。
  • 移除左側溢出字符 s[right - pLen]（保證窗口長度不變），更新 windowFreq（若頻率為0則直接刪除鍵，避免干擾比較）。
  1. 頻率匹配判斷：
  • 自定義 isFreqEqual 函數，通過對比兩個哈希表的鍵數量和對應頻率，判斷是否為異位詞。

時間複雜度與空間複雜度

  • 時間複雜度：O(sLen * k)，其中 sLen 是 s 的長度，k 是 p 中不同字符的數量（哈希表鍵的數量）。每個字符最多被加入和移除窗口各一次，每次頻率比較需遍歷 k 個鍵。
  • 空間複雜度：O(k)，兩個哈希表最多存儲 k 個鍵（k 為 p 中不同字符的數量）。

適用場景

當字符串 s 和 p 包含 任意字符（如大寫字母、數字、符號等）時，無法用固定大小的數組統計頻率，此時哈希表實現更通用。例如：

  • 輸入 s = "aBcAbC", p = "abc"（包含大寫字母）
  • 輸入 s = "12321", p = "321"（包含數字）

這種實現通過哈希表靈活記錄字符頻率，結合滑動窗口高效匹配異位詞，兼顧了通用性和效率。