面试经典150题——滑动窗口

---

1、长度最小的子数组

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[nums_l, nums_l+1, …, nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
提示：

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

1.3 解题代码

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;int right = -1;int n = nums.length;int sum = 0;int min_len = n + 1;while(right < n - 1){++right;sum += nums[right];while(sum >= target){min_len = Math.min(min_len, right - left + 1);sum -= nums[left];left++;} }if(min_len == n + 1){return 0;}return min_len;}
}

1.4 解题思路

1. 使用滑动窗口解决问题。
2. 滑动窗口向右移动，右指针移动，总和增加的，一旦总和大于等于目标值，左指针开始移动，每次移动前都更新一下长度，然后更新sum值（减少），直到sun值小于target后重新开始移动右指针。

2、无重复字符的最长子串

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

提示：

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

2.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;}
}

2.4 解题思路

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

3、串联所有单词的子串

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

• s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 - “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

提示：

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

3.3 解题代码

3.4 解题思路

4、最小覆盖子串

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

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

4.3 解题代码

在这里插入代码片

4.4 解题思路

。