????????這里我也是沒有太懂,只懂個大概,先統計p和當前窗口的字符,后主要在窗口大小固定為?p.length()
,在?s
?上滑動做文章,在s里找到p的長度大小,最后直接比較兩個頻率數組來判斷異位詞
定長窗口做法
class Solution {public List<Integer> findAnagrams(String s, String p) {// 存儲結果的列表List<Integer> ans = new ArrayList<>();// 創建兩個計數器數組,用于統計字符出現頻率int[] cntP = new int[26]; // 統計字符串 p 的字符頻率int[] cntS = new int[26]; // 統計 s 的子串的字符頻率// 統計 p 中每個字符的出現次數for (char c : p.toCharArray()) {cntP[c - 'a']++; // 將字符映射到 0-25 的索引}// 使用滑動窗口遍歷字符串 sfor (int right = 0; right < s.length(); right++) {// 將當前字符加入窗口(右邊界擴展)cntS[s.charAt(right) - 'a']++;// 計算當前窗口的左邊界int left = right - p.length() + 1;// 如果窗口長度不足 p.length(),跳過后續處理if (left < 0) {continue;}// 檢查當前窗口是否是 p 的異位詞if (Arrays.equals(cntS, cntP)) {ans.add(left); // 如果是,記錄起始索引}// 將左邊界字符移出窗口(為下一次窗口滑動做準備)cntS[s.charAt(left) - 'a']--;}return ans;}
}