題目：

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

?

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

?

The order of output does not matter.

?

Example 1:

?

Input:

s: "cbaebabacd" p: "abc"

?

Output:

[0, 6]

?

Explanation:

The substring with start index = 0 is "cba", which is an anagram of "abc".

The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

?

Input:

s: "abab" p: "ab"

?

Output:

[0, 1, 2]

?

Explanation:

The substring with start index = 0 is "ab", which is an anagram of "ab".

The substring with start index = 1 is "ba", which is an anagram of "ab".

The substring with start index = 2 is "ab", which is an anagram of "ab".

?

解題思路：

這道題一個最重要的難點就是時間控制。另一個就是哈希表的應用。

筆者第一次是從s中逐步截取與p等長的子串m，然后再暴力遍歷分析m和p是否為Anagrams（只有字符順序不同的兩個字符串），總的時間復雜度為O(s*p*p)大概是O(n^3)，自然不能通過。第二次時間優化是在比較m和p時，采用《如何判斷兩個String是否是Anagrams》一文中介紹的方法，總的時間復雜度是O(s*p)，大概是O(n^2)，然后依然沒有通過，超時。

最后一次進一步優化，使用滑動窗口，使得時間復雜度為為O(n)，這就是算法的力量！

算法介紹：

（1）NumberOfDeference = p.length()，用來表示目前窗口中的字符和p的差異度（由于窗口最大時（為p.length()）才有可能使NumberOfDeference為0，所以NumberOfDeference 為0時窗口中與p為Anagrams）。NumberOfDeference差異度的含義：一開始窗口左右指針都指向第一個，所以差異度最大為p.length()；當窗口中進來一個p中有的字符，差異度就減一，出去一個有的差異度就增一；至于進來或出去的是p中沒有的則NumberOfDeference不變，反正窗口的最大值也不過是p.length()。

（2）窗口的左右兩個指針：left和right，分別指向窗口的左端和右端。

滑動窗口具體操作：

先滑動右指針，

1.1 加進來的字符如果該字符在數組asciiChars的計數中非負，則NumberOfDeference減一，否則不做操作，

1.2無論在不在數組asciiChars該字符相應位置計數都減一

1.3如果滑動完right，判斷如果窗口長度到達p.length()（如果長度到達p.length()，并且NumberOfDeference為0，則將此時的left值加入到result中），滑動左窗口。

滑動左指針：

2.1被踢出窗口的那個字符如果在數組asciiChars的計數中非負，則NumberOfDeference增一，不在則不做操作。

2.2無論在不在數組asciiChars該字符相應位置計數都加一

（3）上面1.1和2.1操作的原理：asciiChars中的記錄的數據是代表p中含有的的每個字符的數量去掉當前窗口中存在的p字符串中每個字符的數量，一開始窗口大小為0，啥都不存在，自然asciiChars中記錄的就是全部p中含有的的每個字符的數量，如果窗口中有一個，則asciiChars相應的記錄中就少一個。如果窗口中多包含一個p中沒有的（或者包含的某一個字符的數量比p中有的還多），那么這時候，asciiChars中相應的記錄值就會變成負數，代表當前窗口中包含相應字符的“多余”的數量。

??????所以當進來一個的時候，如果相應記錄為非負，那么這個進入是有意義的，則差異度（NumberOfDeference）減一；當出去一個的時候，如果相應記錄為非負，那么這個出去是有意義的，則差異度（NumberOfDeference）加一。

（4）asciiChars用到哈希表思想，用來記錄p中每一種字符分別有多少個。詳見《如何判斷兩個String是否是Anagrams》一文。

代碼：

public static List<Integer> findAnagrams(String s, String p) {List<Integer> result = new ArrayList<Integer>();int NumberOfDeference = p.length(); //差異度指數int left=0,right=0; //窗口左右指針int[] asciiChars = new int[256]; //記錄p中字符有哪些及其數量的數組for (int i = p.length() - 1; i>=0; --i){ ++asciiChars[p.charAt(i)]; } //記錄完畢for(;right<s.length();right++){ //滑動右窗口asciiChars[s.charAt(right)]--; //在該字符相應位置減一if(asciiChars[s.charAt(right)]>=0) NumberOfDeference--; //如果加進來的那個在p中，NumberOfDeference減一if(right-left == (p.length()-1)){//如果這時窗口大小為p.length()if(NumberOfDeference==0) result.add(left); //這時出現一次匹配，將左窗口加到result中//下面是滑動左窗口的操作if(asciiChars[s.charAt(left)]>=0) {NumberOfDeference++; //如果被踢出的那個在p中，NumberOfDeference加一 }asciiChars[s.charAt(left)]++; //數組中相應字符計數位置加回來left++; //左窗口向右滑動 }}return result;}

?

轉載于:https://www.cnblogs.com/tanfd/p/6099463.html

總結

以上是生活随笔為你收集整理的leetcode_438_Find All Anagrams in a String_哈希表_java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。