文章目录
- 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 * 104
- 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 解题思路
- 滑动窗口解决该问题。
- 右指针右移，如果当前所指的字符不在集合里面，直接把该字符添加进字符中；如果当前所指的字符在集合里面，去除左指针所指的字符，并右移动，直到右指针所指的字符在集合中查询不到，最后再将右指针所指的字符添加进去。
- 再上述操作执行完毕后更新一下最长的长度。
2. 找到字符串中所有字母异位词
2.1 题目链接
点击跳转到题目位置
2.2 题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
提示:
- 1 <= s.length, p.length <= 3 * 104
- 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 解题思路
- 定长滑动窗口问题。
- 用哈希表来统计滑动窗口中各字符的数量，统计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] <= 104
- 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 解题思路
- 使用双端队列解决问题，队列存放元素的下标。
- 先遍历前面k个元素，如果队列非空，并且当前的元素大于等于队尾的下标所对应的元素，则删除该元素（因为当前遍历的位置是滑动窗口末尾的元素，如果之前的元素不如当前元素值大，那么滑动窗口的最大值一定不是之前的元素）。之后将当前元素的下标存放进入队列的尾部。
- 结果数组第一位数即为队首元素。
- 之后从数组的第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 <= 105
- 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 解题思路
- 标准的滑动窗口+哈希表。
- 首先先用哈希表统计t中每种字符的长度，然后用一个标记idx用来判断窗口中包含t中的多少个元素。
- 右端移动，直到idx减少为0的时候移动左端，在移动前，先记录当前窗口大小，如果小于min_len,记录当前左端，并且更新min_len，移动左端，直到移动后的idx大于0.
- 移动窗口时，变化的是哈希表中对应存在字符的大小，如果减少到0后继续减少，idx不减少，否则idx会做相应的减少。
