LeetCode热题100——滑动窗口/子串

文章目录 1. 无重复字符的最长子串1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2. 找到字符串中所有字母异位词2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、和为 K 的子数组3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路 4. 滑动窗口最大值4.1 题目链接4.2 题目描述4.3 解题代码4.4 解题思路 5. 最小覆盖子串5.1 题目链接5.2 题目描述5.3 解题代码5.4 解题思路

---

1. 无重复字符的最长子串 1.1 题目链接

点击跳转到题目位置

1.2 题目描述

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

提示：

0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成 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 解题思路 滑动窗口解决该问题。右指针右移，如果当前所指的字符不在集合里面，直接把该字符添加进字符中；如果当前所指的字符在集合里面，去除左指针所指的字符，并右移动，直到右指针所指的字符在集合中查询不到，最后再将右指针所指的字符添加进去。再上述操作执行完毕后更新一下最长的长度。 2. 找到字符串中所有字母异位词 2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

1 <= s.length, p.length <= 3 * 104s 和 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 解题思路 定长滑动窗口问题。用哈希表来统计滑动窗口中各字符的数量，统计p字符的数量，如果字符数量相等，则将字符串中第一个字符的下标放入结果数组中。 3、和为 K 的子数组 3.1 题目链接

点击跳转到题目位置

3.2 题目描述

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

提示：

1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107 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 解题思路 哈希表+前缀和。首先先将哈希表中0的个数设置为1。每次统计当前前缀和，将哈希表中的值+1。累计统计结果，每次加上当前哈希表中 前缀和 - k 的数量。 4. 滑动窗口最大值 4.1 题目链接

点击跳转到题目位置

4.2 题目描述

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

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

提示：

1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= 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 解题思路 使用双端队列解决问题，队列存放元素的下标。先遍历前面k个元素，如果队列非空，并且当前的元素大于等于队尾的下标所对应的元素，则删除该元素（因为当前遍历的位置是滑动窗口末尾的元素，如果之前的元素不如当前元素值大，那么滑动窗口的最大值一定不是之前的元素）。之后将当前元素的下标存放进入队列的尾部。结果数组第一位数即为队首元素。之后从数组的第k位遍历到最后一位，前面的操作与2中操作一致，之后要对队首进行处理，如果队首的下标在当前滑动窗口的左边，则要删除队首元素，之后将滑动窗口内最大值（即为队首元素对应的元素）赋值给结果数组。 5. 最小覆盖子串 5.1 题目链接

点击跳转到题目位置

5.2 题目描述

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

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

提示：

m == s.lengthn == t.length1 <= m, n <= 105s 和 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 解题思路 标准的滑动窗口+哈希表。首先先用哈希表统计t中每种字符的长度，然后用一个标记idx用来判断窗口中包含t中的多少个元素。右端移动，直到idx减少为0的时候移动左端，在移动前，先记录当前窗口大小，如果小于min_len,记录当前左端，并且更新min_len，移动左端，直到移动后的idx大于0.移动窗口时，变化的是哈希表中对应存在字符的大小，如果减少到0后继续减少，idx不减少，否则idx会做相应的减少。