---

1. 无重复字符的最长子串

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。

提示：

• 0 <= s.length <= 5 * 10⁴
• s 由英文字母、数字、符号和空格组成

1.3 解题代码

class Solution {public int lengthOfLongestSubstring(String s) {int left = 0;int right = -1;int n = s.length();int len = 0;Set<Character> hash = new HashSet<Character>();while(right < n - 1){++right;char ch = s.charAt(right);if(!hash.contains(ch)){hash.add(ch);} else{while(hash.contains(ch)){hash.remove(s.charAt(left));++left;}hash.add(ch);}len = Math.max(len, right - left + 1);}return len;}
}

1.4 解题思路

1. 滑动窗口解决该问题。
2. 右指针右移，如果当前所指的字符不在集合里面，直接把该字符添加进字符中；如果当前所指的字符在集合里面，去除左指针所指的字符，并右移动，直到右指针所指的字符在集合中查询不到，最后再将右指针所指的字符添加进去。
3. 再上述操作执行完毕后更新一下最长的长度。

2. 找到字符串中所有字母异位词

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
提示:

• 1 <= s.length, p.length <= 3 * 10⁴
• s 和 p 仅包含小写字母

2.3 解题代码

class Solution {boolean judge(int[] hash1, int[] hash2){for(int i = 0; i < 26; ++i){if(hash1[i] != hash2[i]){return false;}}return true;}public List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();if(s.length() < p.length()){return res;}int[] hash1 = new int[26];int[] hash2 = new int[26];for(int i = 0; i < p.length(); ++i){hash1[s.charAt(i) - 'a']++;hash2[p.charAt(i) - 'a']++;}if(judge(hash1, hash2) == true){res.add(0);}int left = 0;int right = p.length() - 1;while(right < s.length() - 1){right++;hash1[s.charAt(left) - 'a']--;hash1[s.charAt(right) - 'a']++;left++;if(judge(hash1, hash2) == true){res.add(left);}}return res;}
}

2.4 解题思路

1. 定长滑动窗口问题。
2. 用哈希表来统计滑动窗口中各字符的数量，统计p字符的数量，如果字符数量相等，则将字符串中第一个字符的下标放入结果数组中。

3、和为 K 的子数组

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

提示：

• 1 <= nums.length <= 2 * 10⁴
• -1000 <= nums[i] <= 1000
• -10⁷ <= k <= 10⁷

3.3 解题代码

class Solution {public int subarraySum(int[] nums, int k) {HashMap<Integer, Integer> hash = new HashMap<>();int num = 0;int ret = 0;hash.put(0, 1);for(int i = 0; i < nums.length; ++i){num += nums[i];if(hash.containsKey(num - k)){ret += hash.get(num - k);}hash.put(num, hash.getOrDefault(num, 0) + 1);}   return ret;}
}

3.4 解题思路

1. 哈希表+前缀和。
2. 首先先将哈希表中0的个数设置为1。
3. 每次统计当前前缀和，将哈希表中的值+1。
4. 累计统计结果，每次加上当前哈希表中 前缀和 - k 的数量。

4. 滑动窗口最大值

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

提示：

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

4.3 解题代码

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> deque = new LinkedList<Integer>();int n = nums.length;int[] ret = new int[n - k + 1];for(int i = 0; i < k; ++i){while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);}ret[0] = nums[deque.peekFirst()];for(int i = k; i < n; ++i){while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);while(!deque.isEmpty() && i - deque.peekFirst() + 1 > k){deque.pollFirst();}ret[i - k + 1] = nums[deque.peekFirst()]; }return ret;}
}

4.4 解题思路

1. 使用双端队列解决问题，队列存放元素的下标。
2. 先遍历前面k个元素，如果队列非空，并且当前的元素大于等于队尾的下标所对应的元素，则删除该元素（因为当前遍历的位置是滑动窗口末尾的元素，如果之前的元素不如当前元素值大，那么滑动窗口的最大值一定不是之前的元素）。之后将当前元素的下标存放进入队列的尾部。
3. 结果数组第一位数即为队首元素。
4. 之后从数组的第k位遍历到最后一位，前面的操作与2中操作一致，之后要对队首进行处理，如果队首的下标在当前滑动窗口的左边，则要删除队首元素，之后将滑动窗口内最大值（即为队首元素对应的元素）赋值给结果数组。

5. 最小覆盖子串

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 10⁵
• s 和 t 由英文字母组成

5.3 解题代码

class Solution {public String minWindow(String s, String t) {HashMap<Character, Integer> hash = new HashMap<>();int left = 0;int right = -1;int m = s.length();int n = t.length();int idx = n;int min_len = m + 1;int ans = -1;for(int i = 0; i < n; ++i){hash.put(t.charAt(i), hash.getOrDefault(t.charAt(i), 0) + 1);}while(right < m - 1){right++;char ch = s.charAt(right);if(hash.containsKey(ch)){if(hash.get(ch) > 0){idx--;}hash.put(ch, hash.getOrDefault(ch, 0) - 1);if(idx == 0){while(left <= right){if(right - left + 1 < min_len){min_len = right - left + 1;ans = left;}     char ch1 = s.charAt(left);left++;if(hash.containsKey(ch1)){hash.put(ch1, hash.getOrDefault(ch1, 0) + 1);if(hash.get(ch1) > 0){idx++;break;} }}}}}return ans == -1 ? "" : s.substring(ans, ans + min_len);}
}

5.4 解题思路

1. 标准的滑动窗口+哈希表。
2. 首先先用哈希表统计t中每种字符的长度，然后用一个标记idx用来判断窗口中包含t中的多少个元素。
3. 右端移动，直到idx减少为0的时候移动左端，在移动前，先记录当前窗口大小，如果小于min_len,记录当前左端，并且更新min_len，移动左端，直到移动后的idx大于0.
4. 移动窗口时，变化的是哈希表中对应存在字符的大小，如果减少到0后继续减少，idx不减少，否则idx会做相应的减少。