1. 长度最小的子数组
题目描述：
解法一：暴力枚举出所有的子数组的和（会超时）
算法思路：（时间复杂度）
从前往后枚举数组中的任意一个元素，把它当成起始位置，然后从这个起始位置开始，寻找一段最短的区间，使得这段区间的和大于等于目标值
将所有元素作为起始位置所得到的结果中，找到最小值即可
class Solution {public int minSubArrayLen(int target, int[] nums) {//记录结果int ret = Integer. MAX_VALUE;int n = nums.length;//枚举出所有满足和大于等于 target 的子数组[start, end]//由于是取到最小，因此枚举的过程中要尽量让数组的长度最小//枚举开始位置for (int start = 0; start < n; start++) {int sum = 0; //记录从这个位置开始的连续数组的和//寻找结束位置for (int end = start; end < n; end++) {sum += nums[end]; //将当前位置加上if (sum >= target) { //当这段区间内的和满足条件时//更新结果，start 开头的最短区间已经找到，后续即使再有满足大于等于 target 的区间，也不是最短区间了，所以直接跳出本次循环ret = Math.min(ret, end - start + 1);break;}}}return ret == Integer.MAX_VALUE ? 0 : ret;}
}解法二：滑动窗口（利用单调性，使用“同向双指针”来优化）
图解：
tip：像这样 left 和 right 一直往前走，不回退的场景才可以使用 “滑动窗口”！
代码实现：
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;int right = 0;int n = nums.length;int sum = 0;int len = Integer.MAX_VALUE;for ( ; right < n; right++) {sum += nums[right]; //进窗口while (sum >= target) { //判断len = Math.min(len, right - left + 1); //更新结果sum -= nums[left]; //出窗口left++;}}//若循环结束后，len 没变，说明没有满足条件的子数组return len == Integer.MAX_VALUE ? 0 : len;}
}时间复杂度：，虽然有两个循环，但是时间复杂度低，具体原因如下补充
空间复杂度：，只使用了有限的几个变量
补充：为何滑动窗口可以解决问题，并且时间复杂度更低？
2. 无重复字符的最长字串
题目描述：
解法一：暴力枚举 + 哈希表（判断字符是否重复出现）
时间复杂度：
算法思路：
枚举【从每一个位置】开始往后，无重复字符的子串可以到达什么位置，找出其中长度最大的即可
在往后寻找无重复字串能到达的位置时，可以利用【哈希表】统计出字符出现的频次来判断什么时候字串出现了重复元素
class Solution {public int lengthOfLongestSubstring(String s) {int len = 0;char[] arr = s.toCharArray();int n = arr.length;//枚举从不同位置开始的无重复子串//枚举起始位置for (int i = 0; i < n; i++) {//创建一个哈希表，统计频次int[] hash = new int[128];//寻找结束位置for (int j = i; j < n; j++) {hash[arr[j]]++; //统计字符出现的频次if (hash[arr[j]] > 1) { //如果出现重复的字符break;}//如果没有重复，更新 lenlen = Math.max(len, j - i + 1);}}return len;}
}解法二：滑动窗口
研究对象是一段连续的区间，且能通过不回退的 left 和 right 双指针解决问题，因此使用【滑动窗口】思想来优化上述暴力枚举
滑动窗口需满足：窗口内所有元素都是不重复的
思路：
代码实现：
class Solution {public int lengthOfLongestSubstring(String s) {char[] arr = s.toCharArray(); //将字符串转为字符数组//没必要真的创建一个 hash 表，所以用数组模拟哈希表//例如：49 下标处为 2，则表示 ASCII 码为 49 的字符出现了 2 次//数组大小为 128，足够表示常用的字符int[] hash = new int[128];int left = 0;int right = 0;int len = 0;int n = arr.length;while (right < n) {hash[arr[right]]++; //进入窗口（让字符进入哈希表）while (hash[arr[right]] > 1) { //判断（若窗口内出现重复字符）hash[arr[left]]--; //出窗口（让字符离开哈希表）left++;}len = Math.max(len, right - left + 1); //更新结果right++; //让下一个字符进入窗口}return len;}
}时间复杂度：
空间复杂度：，（因为 char[] arr = s.toCharArray();）
3. 最大连续 1 的个数 III
题目描述：
解法一：暴力枚举 + zero 计数器（会超时）
代码实现：
class Solution {public int longestOnes(int[] nums, int k) {int n = nums.length;int len = 0;for (int left = 0; left < n; left++) { //从头开始遍历数组int zero = 0; //记录子数组中 0 的个数for (int right = left; right < n; right++) { //每次从 left 下标处开始向后遍历if (nums[right] == 0) { //统计 0 的个数zero++;}if (zero > k) { //若 0 的个数超过 k，则跳出本次循环，回到外层 for 循环break;}len = Math.max(len, right - left + 1); //更新子数组的最长长度}}return len;}
}解法二：滑动窗口
算法思路：
此题万万不能想着怎样去翻转，否则很复杂，此题可以简单的理解为一段连续的 1 中间塞了 k 个 0
因此，我们可以把问题转化为：求数组中一段最长的连续区间，要求这段区间内 0 的个数不超过 k 个
既然是连续区间，就可以考虑使用【滑动窗口】来解决问题
算法流程：
代码实现：
错误代码总结：
//错误版本总结：
class Solution {public int longestOnes(int[] nums, int k) {int n = nums.length;int left = 0;int right = 0;int zero = 0;int len = 0;while (right < n) {if (nums[right] == 0) {zero++;}//错误一：zero 只要小于等于 k 就可以继续往下执行了，不用非得减到零！if (zero > k) {while (left < right - 1) {left++;if (nums[left] == 0) {zero--;}}}right++; //错误二：要先计算 len 的值，之后再 right++ ！len = Math.max(len, right - left + 1);}return len;}
}正确代码：
class Solution {public int longestOnes(int[] nums, int k) {int left = 0;int right = 0;int n = nums.length;int len = 0; //记录子数组的最大长度int zero = 0; //记录子数组中 0 的个数while (right < n) {if (nums[right] == 0) { //进窗口，当 right 下标处值为 0 时，计数器 + 1zero++;}//判断，当计数器 > k 时，left 左移//若此时 left 下标处值为 1，不进行处理//若此时 left 下标处值为 0，计数器 - 1while (zero > k) {if (nums[left] == 0) {zero--;}left++;}//更新数组最大长度len = Math.max(len, right - left + 1);right++;}return len;}
}4. 将 x 减到 0 的最小操作数
题目描述：
解法一：暴力枚举（会超时）
class Solution {public int minOperations(int[] nums, int x) {int sum1 = 0; //记录数组中所有元素之和for (int a : nums) {sum1 += a;}int n = nums.length;//找出最长的子数组的长度 len，使得其中所有元素的和等于 sum1 - xint target = sum1 - x;if (target == 0) { //该情况为数组所有元素之和 等于 xreturn n;}int len = -1; //记录满足条件的数组长度int sum2 = 0; //记录当前 [i, j] 范围内数组元素之和//第一层 for 循环，遍历数组for (int i = 0; i < n; i++) {sum2 = 0;//第二层 for 循环，遍历从 i 下标开始往后的数组元素for (int j = i; j < n; j++) {sum2 += nums[j];if (sum2 == target) {len = Math.max(len, j - i + 1);break;}if (sum2 > target) {break;}}}if (len == -1) {return -1;} else {return n - len;}}
}解法二：滑动窗口
（正难则反）：题目要求的是数组【左端+右端】两端连续的、和为 x 的最短数组，信息量很多（既要考虑左右端移除元素的时机，又要求最短），不易解答；因此我们可以转换为求数组内一段连续的、和为 sum1 - x 的最长数组 arr（注：此处 sum1 为数组所有元素之和），这样令整个数组长度减去 arr 的长度，即可得到结果
算法流程：
1) 转化问题：求 target = sum1 - x，如果 target < 0，就没有单调性可言，问题无解
2) 初始化左右指针 left = 0，right = 0，记录当前滑动窗口内数组和的变量 sum2 = 0（tip：区分 sum1 和sum2），记录当前满足条件数组的最大区间长度 len = -1
3) 当 right 小于数组长度时，一直循环：
a) 如果 sum2 < target，右移右指针，直至 sum2 大于等于 target，或右指针已经移到数组外
b) 如果 sum2 > target，左移左指针，直至 sum2 小于等于 target，或左指针已经移到数组外
c) 如果经过前面两步的左右移动使得 sum2 == target，则更新满足条件数组的最大长度，并 right++，让下一个元素进入窗口
4) 循环结束后，若 len 的值有意义，则返回 【数组长度 - len】；否则返回 -1
代码实现：
class Solution {public int minOperations(int[] nums, int x) {int n = nums.length; //数组长度int sum1 = 0; //记录整个数组的和for (int i : nums) {sum1 += i;}int left = 0;int right = 0;int len = 0; //统计最长子数组的长度（其中所有元素的和等于 sum1 - x）int target = sum1 - x;if (target < 0) { //如果数组中所有元素相加和都小于 x，说明没有满足条件的结果return -1;}int sum2 = 0; //记录当前[left, right]数组中元素的和while (right < n) {sum2 += nums[right]; //进窗口while (sum2 > target) { //判断sum2 -= nums[left]; //出窗口left++;}if (sum2 == target) { //更新结果len = Math.max(len, right - left + 1);}right++;}if (len == 0) {return -1;}return n - len;}
}时间复杂度：
空间复杂度：
5. 水果成篮
题目描述：
解法一：暴力枚举 + 哈希表（会超时）
代码实现：
class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;int kinds = 0; //记录 hash 数组中果树种类的个数int len = 0; //记录最大采集果树数量for (int i = 0; i < n; i++) {int[] hash = new int[n + 1]; //存放果树种类，每次内层循环结束之后，需重置kinds = 0; //内层循环结束之后，需要重置 hash 数组中果树种类的个数for (int j = i; j < n; j++) {if (hash[fruits[j]] == 0) { //若 hash 中 fruits[j] 处的值为 0 说明这是新种类的树kinds++;}hash[fruits[j]]++; //标志当前种类的树已经出现几次if (kinds > 2) {break;}len = Math.max(len, j - i + 1);}}return len;}
}解法二：滑动窗口
代码实现：
1) 数组模拟哈希表
class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;//hash 的下标表示果树的种类，下标处的值表示该种类果树出现了几次int[] hash = new int[n + 1]; //存放窗口内水果的种类（使用数组模拟哈希表）int left = 0;int right = 0;int len = 0; //记录能采摘果树棵树的最大值int kinds = 0; //记录窗口内水果种类个数while (right < n) {if (hash[fruits[right]] == 0) { //维护水果种类kinds++; //若是 hash 中 fruits[right] 处的果树种类是第一次出现，那么当前窗口内的果树种类 +1}hash[fruits[right]]++; //进窗口（hash 中 fruits[right] 处的果树出现次数 +1）while (kinds > 2) { //判断（当前窗口内果树种类超过 2 时）hash[fruits[left]]--; //出窗口（将 hash 中 fruits[left] 下标种类的果树 出现次数 -1if (hash[fruits[left]] == 0) { //当 hash 中 fruits[left] 下标种类的果树出现次数减为 0 后，当前窗口的果树种类 -1kinds--;}left++; //left 右移，直到窗口内果树种类小于等于 2}len = Math.max(len, right -left + 1); //更新结果right++;}return len;}
}2) 使用容器（HashMap）
//时间复杂度：O(N)
//空间复杂度：O(N)
class Solution {public int totalFruit(int[] fruits) {Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); //统计窗口内水果的种类int len = 0;int left = 0;int right = 0;for ( ; right < fruits.length; right++) {int in = fruits[right];hash.put(in, hash.getOrDefault(in, 0) + 1); //进窗口while (hash.size() > 2) { //判断int out = fruits[left];hash.put(out, hash.get(out) - 1); //出窗口if (hash.get(out) == 0) {hash.remove(out);}left++;}len = Math.max(len, right - left + 1); //更新结果}return len;}
}6. 找到字符串中所有字母异位词
题目描述：
tip：如何快速判断两个字符串是否是“异位词”
利用哈希表，将两个字符串中字符分别放到两个哈希表中，判断其对应字符出现的次数是否相同
解法一：暴力枚举 + 哈希表
解法二：滑动窗口 + 哈希表
算法思路：
因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度与字符串 p 相同长度的滑动窗口，并在滑动中维护窗口中每种字母的数量
当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串1 p 的异位词
可以用两个大小为 26 的数组来模拟哈希表，一个用来保存 s 中的字串每个字符出现的个数，另一个来保存 p 中每一个字符出现的个数，对比两数组来判断两个串是否为异位词
代码实现：
//版本一：比较两个 hash 来确认是否是异位词
class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> list = new ArrayList<>();char[] arr1 = s.toCharArray();char[] arr2 = p.toCharArray();int n1 = arr1.length;int n2 = arr2.length;int[] hash1 = new int[26]; //使用数组模拟哈希表int[] hash2 = new int[26];int left = 0;int right = 0;//将 arr2 中元素通过减字符 a 的方式放到整型数组 hash2 中for (int i = 0; i < n2; i++) {hash2[arr2[i] - 'a']++;}//将 arr1 中 n2 长度的元素放到 hash1 中，判断两 hash 的异同for ( ; right < n1; right++) {int in = arr1[right] - 'a';hash1[in]++; //进窗口if (right - left + 1 > n2) { //判断int out = arr1[left] - 'a'; //出窗口hash1[out]--;left++;}if (check(hash1, hash2)) { //判断两个 hash 的异同list.add(left); //若相同，将该窗口中元素的起始下标添加到 List 中}}return list;}private boolean check(int[] hash1, int[] hash2) {//遍历两数组，若其中元素大小有差异，说明当前窗口内的子串不是字符串 p 的异位词for (int i = 0; i < hash1.length; i++) {if (hash1[i] != hash2[i]) {return false;}}return true;}
}方案二：利用变量 count 存储有效字符个数，看是否等于 p 的长度
class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> list = new ArrayList<>();char[] arr1 = s.toCharArray();char[] arr2 = p.toCharArray();int n1 = arr1.length;int n2 = arr2.length;int[] hash1 = new int[26]; //使用数组模拟哈希表int[] hash2 = new int[26];int left = 0;int right = 0;int count = 0; //记录有效字符个数//将 arr2 中元素通过减字符 a 的方式放到整型数组 hash2 中for (int i = 0; i < n2; i++) {hash2[arr2[i] - 'a']++;}//将 arr1 中 n2 长度的元素放到 hash1 中，判断两 hash 的异同for ( ; right < n1; right++) {int in = arr1[right] - 'a';hash1[in]++; //进窗口//当进行完进窗口操作后，若 hash1 中当前位置的值小于等于 hash2 当前位置的值//说明有效字符数量 +1if (hash1[in] <= hash2[in]) {count++;}if (right - left + 1 > n2) { //判断int out = arr1[left] - 'a';if (hash1[out] <= hash2[out]) {count--;}//在出窗口之前若 hash1 当前下标处的值小于等于 hash2 当前下标处的值//说明有效字符个数和 count 是对等的，若要执行下面出窗口，则 count 也应随之 -1//反之若 hash1 当前下标处的值大于 hash2 当前下标处的值//说明 hash1 此处下标的值为无效字符，不与 count 挂钩，因此 count 不做操作hash1[out]--; //出窗口left++;}if (count == n2) {list.add(left);}}return list;}
}7. 串联所有单词的字串
题目描述：
解法：滑动窗口 + 哈希表
算法思路：
因为 words 中所有字符串长度相同，我们可以将 words 字符数组中的字符串元素看成一个整体，也将字符串 s 按照 words 中一个字符串的长度拆分成若干份
这样就和上一题 “438.找到字符串中所有字母异位词” 相类似，解法也是差不多了，不同的地方有以下几点：
1) 哈希表，上一题中使用的是一个数组模拟哈希表（因为其存储的是一个一个的字符），该题中存储的是一个一个字符串，因此需要借助一个容器（HashMap<String, int>，String 表示该字符串，int 表示该字符串出现的次数）实现
2) left 和 right 指针的移动
在该题中，两指针移动的步长是单词的长度，记为 len（如上图，从 b -> f，而不是从 b -> a），上图示例中的 len 为 3（就是 words 中一个字符串的长度）
3) 滑动窗口执行的次数
滑动窗口循环执行的次数就是单词的长度，记为 len
代码实现：
class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<Integer>();Map<String, Integer> hash1 = new HashMap<String, Integer>(); // 该 hash 存放 words 中所有字符串的频次for (String str : words) {// hash1.getOrDefault(str, 0) + 1 的意思是：// 若 hash1 中已经存在 str，则用已经存在的次数 +1// 否则 0 + 1hash1.put(str, hash1.getOrDefault(str, 0) + 1);}int len = words[0].length();int m = words.length;for (int i = 0; i < len; i++) { // 执行次数// 该 hash 保存窗口内所有单词的频次Map<String, Integer> hash2 = new HashMap<String, Integer>();//细节处理：每次 left 和 right 都要从 i 位置开始，否则每次都一样了int left = i;int right = i;int count = 0;//细节处理：right 的极限位置应该是末尾单词的起始位置，再往后就不是完整的词了，肯定不符合条件//所以判断条件应设为 right + 单词长度小于等于 s 字符串的长度for ( ; right + len <= s.length(); right += len) {// 进窗口 + 维护 countString in = s.substring(right, right + len); //用 in 表示要进窗口的单词hash2.put(in, hash2.getOrDefault(in, 0) + 1); // 该操作意义和上边一样//判断有效字符串个数//if (hash2.get(in) <= hash1.get(in)) { //这样写是错误的//上述写法若 in 在 hash1 中不存在就会报错//下面正确写法，若存在则返回其出现次数，否则返回 0//因为能进这个判断，所以 in 肯定不小于等于 0，所以该操作可行if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {count++;}// 判断if (right - left + 1 > len * m) { //若窗口大小 大于 (words 中一个单词长度乘以数组长度) 的话，出窗口// 出窗口 + 维护 countString out = s.substring(left, left + len); //用 out 表示要出窗口的单词if (hash2.get(out) <= hash1.getOrDefault(out, 0)) { //若滑出窗口字符串为有效字符串，则 count--count--;}hash2.put(out, hash2.get(out) - 1);left += len;}//更新结果if (count == m) { //有效单词个数 等于 words 中所有单词个数时ret.add(left);}}}return ret;}
}tip：该题中所用方法
1) getOrDefault（主要是与 Map 接口相关的实现，如：HashMap、TreeMap等）
V getOrDefault(Object key, V defaultValue)从 Java8 开始，该方法接受两个参数：第一个参数是你想要从 Map 中获取的键，第二个参数是如果该键不存在时应该返回的默认值
2) get（Map 接口中的方法）
V get(Object key)用于根据给定的键（key）检索对应的值（value），如果 Map 中包含该键的映射，则返回对应的值；否则返回 nul
需注意：如果 Map 中的值本身就是 null，那么 get 方法也会返回 null
3) substring（String 类中方法）
用于从字符串中提取子字符串，有以下两种常见用法
1. 使用起始索引：
String str = "Hello, World!";
String subStr = str.substring(7); // 从索引7开始提取，直到字符串结束
System.out.println(subStr); // 输出: World!2. 使用起始索引和结束索引（左闭右开区间）
String str = "Hello, World!";
String subStr = str.substring(7, 12); // 从索引7开始提取，到索引12结束（不包括索引12处的字符）
System.out.println(subStr); // 输出: World8. 最小覆盖字串
题目描述：
解法一：暴力枚举 + 哈希表
在字符串 s 中枚举出所有符合条件（hash1 中出现所有有效字符且次数大于等于 hash2）的子串
取其中最短子串即为最小子串
解法二：滑动窗口 + 哈希表
算法思路：
上述情况中，当 left 左移一个位置后，right 会出现两种情况：
1) left 左移之后，依旧符合要求（比如：left 原来的位置是一个无效字符或重复的有效字符），此时 right 可以不动
2) left 左移之后，不符合要求（比如：left 原来的位置就是当前窗口中不重复的一个有效字符），此时 right 就需要右移继续寻找下一个满足条件的位置
像这种 left 和 right 只前进不回退，有单调性的题可以使用【滑动窗口】
算法流程：
代码优化：
上面 check 判断两 hash 是否相同会遍历一遍 hash1，还会遍历一遍 hash2，时间复杂度是非常高的，因此有以下优化：
使用变量 count 标记有效字符的种类（与上面 “6. 找到字符串中所有字母异位词” 中的 count 标记有效字符的个数不一样）
若是标记有效字符的个数的话，会出现：
因此需标记有效字符出现的种类，且需判断该种类出现的次数：
具体步骤：
代码实现：
class Solution {public String minWindow(String s, String t) {char[] ss = s.toCharArray();char[] tt = t.toCharArray();int[] hash2 = new int[128]; //存储 t 中字符int kinds = 0; //统计 t 中字符种类for (char a : tt) {if (hash2[a] == 0) { //若该种类字符第一次出现，则种类++kinds++;}hash2[a]++; //将 t 中各字符出现次数统计到 hash2 中}int left = 0;int right = 0;int[] hash1 = new int[128]; //存储 [left, right] 中的字符int count = 0; //统计 hash1 中有效字符种类int begin = -1; //记录符合条件子串的起始下标int minLen = Integer.MAX_VALUE;for ( ; right < ss.length; right++) {char in = ss[right];hash1[in]++; //进窗口if (hash1[in] == hash2[in]) { //字符相同，且出现次数相同，则种类++count++;}while (count == kinds) { //判断 hash1 中有效字符个数 count 是否等于 kindsif (right - left + 1 < minLen) { //判断当前窗口中子串长度是否小于已记录的子串长度minLen = right - left + 1; //若条件成立，则更新子串最短长度及起始位置begin = left;}char out = ss[left];//在出窗口之前，先判断当前 hash1 和 hash2 的 left 下标出值是否相同//若相同，则count--（这是因为在出窗口之后，有效字符的种类 -1if (hash1[out] == hash2[out]) {count--;}hash1[out]--; //left 坐标处的字符种类出现次数 -1left++; //出窗口}}if (begin == -1) { //若此时起始位置并未改变过，证明字符串 s 中并没有符合要求的子串return new String();} else { //若有符合要求的子串，则输出[begin, begin + minLen) 的子串return s.substring(begin, begin + minLen);}}
}
