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);
}
}
题目链接
