1. 水果成籃（904）

題目描述：

算法原理：
根據題目意思，friuts表示第i棵樹上的水果種類，然后我們有兩個籃子去在這些樹上去采水果，但是有限制就是一個籃子里就只能裝一種水果，也就是我們在根據fruits數組去采摘水果的時候，水果種類達到第三種的時候就立刻停止采摘。
綜上我們可以先定義一個hash表，類型為（int，int），第一個序號表示水果的種類，第二個序號表示這種水果在籃子中的總數。此時我們就可以將這里的問題想成滑動窗口問題，根據我們之前總結的滑動窗口的問題，不難發現這里的進窗口就是直接根據fruits數組放入水果的過程，當hash表的size也就是水果種類大于2時，就開始出窗口，對于出窗口的過程首先將fruit[left]對應得水果種類在hash表中的數量減一，然后注意如果此時對應種類的水果數量為0那么就要在hash表中移除這種水果也就是hash表的size減一，最后照舊left++，然后重復上述出窗口的操作，直至籃子中的水果種類等于二時跳出，此時籃子中的水果就是滿足題目條件的，因此我們就可以去更新返回值也就是籃子中水果的最大數目。具體看代碼。
代碼如下：

class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;int ret = 0;Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int left = 0, right = 0; right < n; right++) {int in = fruits[right];map.put(in, map.getOrDefault(in, 0) + 1);while (map.size() > 2) {int out = fruits[left];map.put(out, map.get(out) - 1);if (map.get(out) == 0) {map.remove(out);}left++;}ret = Math.max(ret, right - left + 1);}return ret;}
}

題目鏈接

2. 找到字符串中所有字母異位詞（438）

題目描述：

算法原理：
首先明白題目給出的異位詞是什么意思，舉例來說就是"abc"和"bac"互為異位詞，就是說一個字符串如果是另一個字符串打亂順序后的結果就是它的異位詞，很好理解。
然后題目要求我們去在字符串s的子串中去找到字符串p的異位詞，理解了以上內容我們就可以使用滑動窗口的方法去解決這個問題。
我們先使用一個數組來記錄字符串p的各個字符的數量，然后開始基于字符串s來進行進窗口的操作，也是使用一個數組來記錄各個進窗口的字符數量，當進窗口的字符數量超過字符串p中的字符數量時開始出窗口，首先對數組中的s[left]對應字符的數量減一，之后left++，當窗口內的字符數量恢復到p中的字符數量時跳出循環，然后判斷，p字符串的保存各字符數量的數組和此時保存窗口內各字符數量的數組是否相等，如果相等那么此時就更新結果，也就是更新返回的起始索引，即窗口左邊的索引。
代碼如下：

class Solution {public List<Integer> findAnagrams(String ss, String p) {List<Integer> ret = new ArrayList<>();int[] arrP = new int[26];int[] arrS = new int[26];char[] s = ss.toCharArray();for (char ch : p.toCharArray()) {arrP[ch - 'a']++;}int n = ss.length();int m = p.length();for (int left = 0, right = 0; right < n; right++) {arrS[s[right] - 'a']++;while (right - left + 1 > m) {arrS[s[left++] - 'a']--;}if (Arrays.equals(arrP, arrS)) {ret.add(left);}}return ret;}
}

優化：
當我們使用數組比較這種方法來驗證是否當前窗口下的字符構成字符串p的異位詞時，雖然代碼是可以直接使用Arrays類的靜態方法equals來比較，但是內部肯定是需要一個循環來實現的，因此我們對代碼進行優化。
相對于前面的代碼，這里優化的代碼只需要加上一個count變量，這是用來記錄窗口內的有效字符數量。那么什么是有效字符，就是在字符串p中包含的字符，但是一旦加入窗口中的單種字符個數超過字符串p中的對應的字符數量，那么這個字符也不是有效字符。例如字符串p為"abc"此時窗口內字符為"aab"此時有效字符數量為2。
因此在進窗口時對s[right]進行判斷，是否此時窗口內該字符的數量在加一后是小于等于p字符串中相同字符的數量的，只有這樣count才能加一。當窗口內的字符數量超出字符串p的字符數量時開始出窗口，此時也要進行判斷是否s[left]出窗口后，窗口內的對應字符數量是否小于p中相同字符的數量，如果小于count才能減一。跳出出窗口循環后就進行判斷，是否此時窗口內有效字符數量count和p字符長度相等，如果相等就說明窗口內字符是p的異位詞，更新返回結果。
優化后代碼：

class Solution {public List<Integer> findAnagrams(String ss, String p) {List<Integer> ret = new ArrayList<>();int[] arrP = new int[26];int[] arrS = new int[26];char[] s = ss.toCharArray();int count = 0;for (char ch : p.toCharArray()) {arrP[ch - 'a']++;}int n = ss.length();int m = p.length();for (int left = 0, right = 0; right < n; right++) {arrS[s[right] - 'a']++;if (arrS[s[right] - 'a'] <= arrP[s[right] - 'a']) {count++;}while (right - left + 1 > m) {arrS[s[left] - 'a']--;if (arrS[s[left] - 'a'] < arrP[s[left] - 'a']) {count--;}left++;}if (count == m) {ret.add(left);}}return ret;}
}

題目鏈接

3. 串聯所有單詞的子串（30）

題目描述：

算法原理：
這一題和上一題異位詞如出一轍，做題的思想完全一致，只不過上一題進窗口出窗口的單位是字符，這一題則是一個子串，也是用到了上一題當中的優化的使用count計數的方法。然后需要注意一個不一樣的點就是，因為每次進窗口出窗口的字符串單位不一定是總的字符串s的因子，所以為了遍歷各種可能我們需要在最外層再多套上一層循環，具體看代碼。
代碼如下：

class Solution {public List<Integer> findSubstring(String s, String[] words) {int len = words[0].length();int aim = words.length;List<Integer> list = new ArrayList<>();HashMap<String, Integer> hash = new HashMap<>();for (String str : words) {hash.put(str, hash.getOrDefault(str, 0) + 1);}int n = s.length();for (int i = 0; i < len; i++) {HashMap<String, Integer> temp = new HashMap<>();for (int left = i, right = i, count = 0; right + len <= n; right += len) {String in = s.substring(right, right + len);temp.put(in, temp.getOrDefault(in, 0) + 1);if (hash.getOrDefault(in, 0) != 0 && temp.get(in) <= hash.get(in)) {count++;}while (right - left + 1 > aim * len) {String out = s.substring(left, left + len);temp.put(out, temp.get(out) - 1);if (hash.getOrDefault(out, 0) != 0 && temp.get(out) < hash.get(out)) {count--;}left += len;}if (count == aim) {list.add(left);}}}return list;}
}

題目鏈接

4. 最小覆蓋子串（76）

題目描述：

算法原理：
還是根據第二題異位詞的方法，使用count計數的方式來完成這題，但是與前者不同的在于前者要求滿足的子串必須每一個字符及其數量和t要一一對應，但是這一題不一樣，它只需要將t的各個字符包含進子串即可，因此我們這里選擇使用count來表達字符的種類，當窗口內的相應的字符種類達到要求時就進入出窗口的循環。對于返回值的更新直接放到出窗口循環當中了，因為此時的窗口范圍的子串都是滿足題目條件的直接更新就可以了。
代碼如下：

class Solution {public String minWindow(String ss, String tt) {Map<Character, Integer> hash1 = new HashMap<>();Map<Character, Integer> hash2 = new HashMap<>();char[] s = ss.toCharArray();char[] t = tt.toCharArray();for (char ch : t) {hash1.put(ch, hash1.getOrDefault(ch, 0) + 1);}int n = ss.length();int aim = hash1.size();int minL = Integer.MAX_VALUE;int begin = -1;for (int left = 0, right = 0, count = 0; right < n; right++) {char in = s[right];hash2.put(in, hash2.getOrDefault(in, 0) + 1);if (hash1.containsKey(in) && hash1.get(in).equals(hash2.get(in))) {count++;}while (count == aim) {if ((right - left + 1) < minL) {minL = right - left + 1;begin = left;}char out = s[left];hash2.put(out, hash2.get(out) - 1);if (hash1.containsKey(out) && hash2.get(out) < hash1.get(out)) {count--;}left++;}}return begin == -1 ? "" : ss.substring(begin, begin + minL);}
}

題目鏈接