【算法一周目】滑动窗口（1）
目录
长度最小的子数组
解题思路
代码实现
无重复字符的最大字串
解题思路
代码实现
最大连续1的个数l l l
解题思路
代码实现
将x减到0的最小操作数
解题思路
代码实现
长度最小的子数组
题目链接：209. 长度最小的子数组
题目描述：
给定一个含有 n 个正整数的数组 nums 和一个正整数 target。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。
解题思路
解法一：暴力求解
枚举所有可能的子数组，计算子数组的和，检查是否大于等于 target ，找到符合题目要求的长度最小的子数组。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = INT_MAX;
for (int left = 0; left < n; ++left) {
int sum = 0;
for (int right = left; right < n; ++right) {
sum += nums[right];
if (sum >= target) {
ret = min(ret, right - left + 1);
break;
}
}
}
return ret == INT_MAX ? 0 : ret;
}
};
暴力解法简单粗暴，但是由于时间复杂度是 O(n ^ 2)，一旦数据量比较大，必定会超时
解法二：滑动窗口
滑动窗口其实也是基于暴力解法优化而来，滑动窗口的核心就是想办法让暴力解法中的 right 指针不回退，一直往前走。
我们想想这样一个问题，在暴力解法中，当left和right找到一个合法的子数组后，left++，right有必要回退到left位置吗？答案是没有必要的，当left++后，left和right区间的子数组的和可能大于等于target，也可能小于target。我们可以让left一直++，并在此过程中记录区间长度，直到left和right区间的子数组的和小于target，然后再让right++，增大区间长度的和，重复上述过程，直到遍历完数组。
滑动窗口具体过程如下：
- 1.初始化left和right指针为0。
- 2.进窗口：计算区间的和
- 3.判断：
- 当区间和大于等于target时，找到合法区间，更新结果，出窗口：让left++，重复判断-更新结果过程，直到区间和小于target；
- 当区间和小于target时，进窗口：让right++，计算区间和。
- 4.重复上述过程，直到right遍历完数组。
值得注意的是，更新结果这步不是固定的，有时候在判断时更新，有时候在判断完后再更新。
代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0, n = nums.size(), len = INT_MAX;
for(int left = 0, right = 0; right < n; right++)
{
sum += nums[right];
while(sum >= target)
{
len = min(len, right - left + 1);
sum -= nums[left++];
}
}
return len == INT_MAX ? 0 : len;
}
};细节：由于求的是长度最小的子数组，所以len要初始化为INT_MAX，不能初始化为0。
时间复杂度：O(n)
空间复杂度：O(1)
无重复字符的最大字串
题目链接：3. 无重复字符的最长子串
题目描述：
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
解题思路
解法一：暴力求解
通过枚举从每个位置开始，向后寻找无重复字符的子串能到达的位置，记录其中最长的子串长度即可。在寻找无重复子串时，可以使用哈希表统计字符出现的频次，遇到重复字符时停止。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret = 0; // 记录结果
int n = s.length();
// 枚举从不同位置开始的无重复子串
for (int i = 0; i < n; i++) {
int hash[128] = { 0 }; // 记录字符频次
for (int j = i; j < n; j++) {
hash[s[j]]++; // 统计字符频次
if (hash[s[j]] > 1) // 出现重复，终止
break;
ret = max(ret, j - i + 1); // 更新结果
}
}
return ret;
}
};
暴力求解的问题还是时间复杂度是O(n)，对于处理数据量比较大的数据时会超时。
解法二：滑动窗口
使用滑动窗口，使得窗口内的字符不重复。
当窗口右端进入新字符时，更新哈希表记录字符频次：
- 如果字符频次大于1，则窗口出现重复字符，开始从左侧收缩窗口，直到字符频次变为1，更新结果。
- 如果没有超过1，说明没有重复字符，直接更新结果。
代码实现
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = { 0 }; // 使用数组模拟哈希表
int left = 0, right = 0, n = s.size(), len = 0;
while(right < n)
{
hash[s[right]]++; // 将右端字符加入窗口
while(hash[s[right]] > 1) //判断
hash[s[left++]]--; //出窗⼝
//更新结果
len = max(len, right - left + 1);
//让下⼀个元素进⼊窗⼝
right++;
}
return len;
}
};细节：由于s由英文字母、数字、符号和空格组成，不必真的使用unordered_map，用一个128大小的数组当作哈希表即可。
时间复杂度：O(n)
空间复杂度：O(1)
最大连续1的个数l l l
题目链接：1004. 最大连续 1 的个数 III
题目描述：
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个0，则返回数组中连续 1的最大个数。
解题思路
根据题目描述，我们可以将其转换为求一段最长的连续子区间，其中0的数量不超过k个，我们用滑动窗口解决。
- 1.初始化左右指针left和right，以及记录0个数的变量cnt。
- 2.当right向右遍历数组时：
- 如果当前元素是0，cnt++；
- 然后判断cnt是否大于cnt，大于则让left++缩减窗口，移除窗口中的0，直到cnt小于等于k。
- 3。此时窗口合法，更新结果。
代码实现
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int ret = 0, cnt = 0, n = nums.size();
for(int left = 0, right = 0; right < n; right++)
{
if(nums[right] == 0) cnt++; //当前元素为0，cnt++
//当cnt > k时，移除窗口中的0，直到cnt <= k
while(cnt > k)
{
if(nums[left] == 0)
cnt--;
left++;
}
//更新结果
ret = max(ret, right - left + 1);
}
return ret;
}
};时间复杂度：O(n)
空间复杂度：O(1)
将x减到0的最小操作数
题目链接：1658. 将 x 减到 0 的最小操作数
题目描述：
给你一个整数数组 nums 和一个整数 x。每次操作时，你可以移除数组 nums 的最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，你需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0，返回最少的操作数；否则，返回 -1。
解题思路
解法：滑动窗口
题目要求的是在数组左端、右端找两段连续且和为x的短数组，我们可以将其转换为在数组中找到和为 sum - x 的最长子数组，其剩余数组长度就是最小操作数，可以使用滑动窗口解决问题。
具体过程如下：
- 1.计算数组的和 sum ，然后求出target = sum - x。这里有个小细节，若target < 0，说明x > sum，不可能找到题目要求的最小操作数，直接返回-1。
- 2.初始化 left 和 righ t两个指针为0，再用一个变量 part_sum 记录区间长度的和。
- 3.当 part_sum > target 时，减小 part_sum，left++，直到 part_sum <= target。
- 4.如果 part_sum == target，更新最长子数组的长度。
- 5.right++，增大 part_sum。
- 循环上述过程，直到 right 遍历完数组。
代码实现
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
//1.计算数组总和
int n = nums.size(), sum = 0;
for(auto e : nums) sum += e;
int len = -1, target = sum - x, part_sum = 0;
if(target < 0) return -1;
//2.使用滑动窗口求出符合条件的最大子数组和
for(int left = 0, right = 0; right < n; right++)
{
part_sum += nums[right];
while(left < n && part_sum > target)
part_sum -= nums[left++];
if(part_sum == target)
len = max(len, right - left + 1);
}
return len == -1 ? -1 : n - len;
}
};拜拜，下期再见😏
摸鱼ing😴✨🎞
