leetcode——滑动窗口
·
209.长度最小的子数组
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于
target的长度最小的子数组
[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组[4,3]是该条件下的长度最小的子数组。示例 2：
输入：target = 4, nums = [1,4,4] 输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
原理
滑动窗口的基本思想
- 滑动窗口技术：用两个指针表示一个窗口，窗口的范围是
[left, right]，我们通过调整这两个指针来扩展或缩小窗口，从而找到满足条件的最小子数组。- 通过右指针扩展窗口，并在每次扩展后检查是否满足条件（子数组和是否大于等于
target）。- 一旦满足条件，就通过左指针收缩窗口，以尝试找到最小的符合条件的子数组。
2. 变量说明
len：记录最小子数组的长度，初始值设为数组长度。若不存在符合条件的子数组，最后返回len即为0。left：滑动窗口的左指针，表示当前子数组的起始位置。right：滑动窗口的右指针，表示当前子数组的结束位置。sum：当前窗口内的元素和，用来判断窗口是否满足target。3. 主体流程
- 外循环：
right指针从 0 开始遍历整个数组，表示窗口的右边界。
- 每次将
nums[right]加到sum上，表示将当前元素加入窗口。- 内循环：每当
sum >= target时，表示当前子数组满足条件（和大于等于target），此时尝试通过移动left指针来缩小窗口，从而找到满足条件的最小子数组。
- 如果当前窗口的和减去左边界的元素
nums[left]依然大于等于target，就可以通过移动左边界来进一步缩小窗口。- 如果不能进一步缩小，说明当前窗口是符合条件的最小窗口，更新最小长度
len并退出内循环。- 结束条件：
- 如果在遍历过程中，窗口的和始终小于
target，说明不存在符合条件的子数组，返回 0。- 如果遍历结束，返回记录的最小子数组长度。
4. 特殊情况处理
- 如果最后找不到符合条件的子数组（即
sum在整个过程中都未能达到target），最终返回值为len，即为nums.length（表示没有找到符合条件的子数组）。时间复杂度分析
- 时间复杂度：O(n)，其中 n 是数组
nums的长度。右指针和左指针最多只会各自遍历数组一次，因此时间复杂度是 O(n)。- 空间复杂度：O(1)，只使用了常数的额外空间。
代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 初始化一些变量
int len = nums.length; // 用于记录最小子数组的长度，初始化为数组长度（如果没有符合条件的子数组，则返回 len）
int left = 0; // 左指针，表示当前滑动窗口的左边界
int sum = 0; // 当前窗口的和
// 遍历整个数组，右指针从 0 遍历到 nums.length
for (int right = 0; right < nums.length; right++) {
sum += nums[right]; // 每次将右边界元素加入窗口，更新总和
// 当当前窗口的总和大于等于 target 时，开始尝试缩小窗口
while (sum >= target) {
// 如果当前窗口的总和减去 nums[left] 依然大于等于 target，就继续移动左边界
if (sum - nums[left] >= target) {
sum -= nums[left]; // 减去左边界元素，缩小窗口
left++; // 左指针右移
} else {
// 否则，当前窗口的总和已经满足条件，记录当前窗口的长度
len = Math.min(len, right - left + 1); // 更新最小长度
break; // 退出当前 while 循环，继续扩展右边界
}
}
// 当右指针到达数组末尾时，如果仍然没有找到符合条件的子数组，返回 0
if (right == nums.length - 1) {
if (sum < target) {
return 0; // 没有符合条件的子数组，返回 0
}
break; // 结束循环
}
}
return len; // 返回最小长度
}
}
904.水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组
fruits表示，其中fruits[i]是第i棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组
fruits，返回你可以收集的水果的 最大 数目。示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。示例 2：
输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。示例 3：
输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。提示：
1 <= fruits.length <= 1050 <= fruits[i] < fruits.length
原理
滑动窗口算法
- 滑动窗口：我们使用滑动窗口的技术，通过
left和right两个指针来表示当前子数组的左右边界。我们不断扩展右边界，并适时移动左边界，以保证每次窗口内最多有两种水果种类。2. 关键变量说明
left和right：分别表示窗口的左边界和右边界，右指针不断向右扩展，左指针根据需要向右移动，以保证窗口内的水果种类不超过两种。type1和type2：表示当前两个篮子里的水果类型。初始值设为-1，表示篮子为空。index1和index2：分别记录type1和type2对应水果最后出现的位置。用于在需要收缩窗口时，判断应该收缩哪个篮子。trees：记录在遍历过程中，可以采摘的最大水果数量。3. 主体逻辑
初始化：首先初始化
left和right为 0，表示滑动窗口的开始位置。type1和type2设置为 -1，表示两个篮子还没有水果。index1和index2初始化为 0，表示水果的最后位置。遍历数组：
- 右指针扩展：
right指针每次遍历到下一个水果时，尝试将水果添加到窗口中，并更新水果类型。- 当窗口包含两种水果时：
- 如果新水果与现有的两种水果都不相同，则需要调整窗口，移除某个水果种类，将当前水果添加到新篮子里。
- 选择性调整左指针：选择移除窗口中更靠左的水果（
index1或index2较小），并移动左指针到该水果的下一个位置。计算最大采摘水果数：
- 每次在窗口内满足条件时，记录当前窗口的水果数量（
right - left + 1），并更新trees为最大值。最终结果：遍历完所有水果后，
trees中保存的即为能采摘的最大水果数量。4. 特殊情况
- 只有一个水果：如果数组只有一个元素，直接返回 1。
- 只有一种水果：如果数组中只有一种水果类型，返回数组的长度。
5. 时间复杂度
- 时间复杂度：O(n)，其中 n 是水果数组的长度。
left和right两个指针各自遍历一次整个数组，因此时间复杂度为 O(n)。- 空间复杂度：O(1)，除了输入数组外，使用了常数的额外空间。
代码
class Solution {
public int totalFruit(int[] fruits) {
// 如果数组中只有一个水果，直接返回 1
if (fruits.length == 1) {
return 1;
}
// 初始化变量
int left = 0, right = 0; // 左右指针，用于滑动窗口
int trees = 0; // 记录最大采摘的水果数
int type1 = -1, type2 = -1; // 用于记录篮子里的水果种类
int index1 = 0, index2 = 0; // 用于记录不同种类水果的最后出现位置
// 遍历数组，用右指针扩展窗口
for (int i = 0; i < fruits.length; i++) {
// 如果篮子1还没有装水果，装上当前水果
if (type1 == -1) {
type1 = fruits[i];
index1 = i;
}
// 如果篮子2还没有装水果，并且当前水果与篮子1的水果不同，装上篮子2
else if (type2 == -1 && fruits[i] != type1) {
type2 = fruits[i];
index2 = i;
trees = Math.max(right - left + 1, trees); // 更新最大水果数
}
else {
// 如果当前水果属于篮子1或者篮子2之一，更新水果种类的最后位置
if (type1 == fruits[i]) {
index1 = i;
}
if (type2 == fruits[i]) {
index2 = i;
}
// 如果当前水果不属于任何一个篮子
if (fruits[i] != type1 && fruits[i] != type2) {
// 记录当前窗口的最大值
trees = Math.max(right - left, trees);
// 找出当前水果出现在左边还是右边，决定调整哪个篮子
if (index1 < index2) {
type1 = fruits[i]; // 更新篮子1的水果类型
left = index1 + 1; // 左指针调整到 index1+1
index1 = i; // 更新篮子1的水果最后位置
} else {
type2 = fruits[i]; // 更新篮子2的水果类型
left = index2 + 1; // 左指针调整到 index2+1
index2 = i; // 更新篮子2的水果最后位置
}
} else {
// 当前水果属于篮子1或篮子2，更新最大水果数
trees = Math.max(right - left + 1, trees);
}
}
right++; // 右指针向右扩展
}
// 如果只有一种水果类型，直接返回水果数组的长度
if (type2 == -1) {
return fruits.length;
}
// 返回最大水果数
return trees;
}
}
76.最小覆盖子串
给你一个字符串
s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。- 如果
s中存在这样的子串，我们保证它是唯一的答案。示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成进阶：你能设计一个在
o(m+n)时间内解决此问题的算法吗？
原理
1. 目标
我们需要在字符串
s中找到一个最小的子串，该子串包含了字符串t中所有的字符，并且t中字符的数量在子串中必须不少于t中相应字符的数量。2. 滑动窗口
我们使用滑动窗口的技术来解决问题。滑动窗口使用两个指针
left和right，right用来扩展窗口，left用来缩小窗口。当窗口内包含所有的t中的字符时，我们记录当前窗口的长度并尽量缩小窗口，以找到最小的子串。3. 字符计数与频次数组
我们用一个数组
arrayt来记录t中每个字符的频次，另外用一个flags数组来标记t中哪些字符需要在s中出现。在滑动窗口的过程中，我们不断更新arrayt中的字符频次，判断当前窗口是否包含了所有t中需要的字符。4. 窗口的扩展与收缩
- 扩展窗口：右指针向右移动，扩展窗口，直到窗口包含了
t中所有的字符。- 收缩窗口：当窗口满足条件时，左指针向右移动，收缩窗口，尽量减少窗口大小，同时更新当前最小窗口的长度。
5. 时间复杂度
- 时间复杂度：O(m + n)，其中
m是字符串s的长度，n是字符串t的长度。由于left和right指针各自最多向右移动一次，所以时间复杂度是 O(m + n)。- 空间复杂度：O(1)，由于我们使用的数组
arrayt和flags的大小是固定的（52），空间复杂度是常数级别。6. 特殊情况
- s 的长度小于 t 的长度：此时
s无法包含t的所有字符，直接返回空字符串。- 没有符合条件的子串：如果没有找到符合条件的子串，返回空字符串。
代码
class Solution {
public static String minWindow(String s, String t) {
// 如果 s 的长度小于 t 的长度，直接返回空字符串
if(s.length() < t.length()){
return "";
}
// 初始化两个字符频次数组
int[] arrayt = new int[52]; // 用于存储 t 中字符的频次
int[] flags = new int[52]; // 用于标记 t 中哪些字符是需要在 s 中找到的
stringFlag(t, flags); // 根据 t 填充 flags 数组，标记 t 中的字符
stringToCharArray(t, arrayt); // 根据 t 填充 arrayt 数组，记录 t 中每个字符的出现频次
int left = 0, right = 0, len = s.length(); // 左右指针，和记录最小子串长度的变量
int[] ans = new int[2]; // 存储最终的最小子串的左右边界
ans[1] = -1; // 初始化结果为 -1，表示没有找到符合条件的子串
// 使用右指针扩展窗口
for(int i = 0; i < s.length(); i++) {
// 当前字符在 t 中出现时，将其频次减少
if(s.charAt(i) < 97) { // 大写字母
arrayt[s.charAt(i) - 65]--;
} else { // 小写字母
arrayt[s.charAt(i) - 71]--;
}
// 判断当前窗口是否包含了 t 中所有的字符
if(isAllLessThanOrEqualToZero(arrayt, flags)) {
// 找到符合要求的子串
int temp = s.charAt(left) < 97 ? s.charAt(left) - 65 : s.charAt(left) - 71;
// 当窗口符合要求时，尽量缩小窗口，左指针向右移动
while(arrayt[temp] <= 0) {
if(right - left + 1 <= len) {
len = right - left + 1;
ans[0] = left;
ans[1] = right;
}
// 还原左边界字符的频次
if(s.charAt(left) < 97) {
arrayt[s.charAt(left) - 65]++;
} else {
arrayt[s.charAt(left) - 71]++;
}
// 更新临时字符的位置
int temp1 = s.charAt(left) < 97 ? s.charAt(left) - 65 : s.charAt(left) - 71;
if(flags[temp1] == 1) {
temp = s.charAt(left) < 97 ? s.charAt(left) - 65 : s.charAt(left) - 71;
}
left++; // 左指针右移，缩小窗口
}
}
right++; // 右指针右移，扩大窗口
}
// 如果没有找到符合条件的子串，返回空字符串
if(ans[1] == -1) {
return "";
}
// 返回最小子串
return s.substring(ans[0], ans[1] + 1);
}
// 判断数组 nums 中的元素是否都小于等于 0，表示是否满足 t 中所有字符的要求
public static boolean isAllLessThanOrEqualToZero(int[] nums, int[] flags) {
for(int i = 0; i < 52; i++) {
if(nums[i] > 0 && flags[i] == 1) { // 只有 t 中出现的字符，才检查其频次
return false;
}
}
return true;
}
// 将字符串 str 转换为字符频次数组 nums，统计字符串 str 中各个字符的频次
public static void stringToCharArray(String str, int[] nums) {
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) < 97) { // 大写字母
nums[str.charAt(i) - 65]++;
} else { // 小写字母
nums[str.charAt(i) - 71]++;
}
}
}
// 将字符串 t 转换为 flags 数组，标记 t 中的字符
public static void stringFlag(String str, int[] flags) {
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) < 97) { // 大写字母
flags[str.charAt(i) - 65] = 1;
} else { // 小写字母
flags[str.charAt(i) - 71] = 1;
}
}
}
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
27
0- 0
已为社区贡献6条内容
所有评论(0)