[算法初阶]第二集 滑动窗口(已完结)
大家好啊,好久没有更新了,最近比较忙,所以来更新初阶算法,正好复习一下,感谢大家的观看,如有错误欢迎指出。
下面我们来看题目吧！
1.209. 长度最小的子数组
这题大家想必一眼就看出了解法一暴力法
这个解法很简单
代码如下,不做多的解释
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;for (int i = 0; i < n; i++) {int sum = 0;for (int j = i; j < n; j++) {sum += nums[j];if (sum >= s) {ans = min(ans, j - i + 1);break;}}}return ans == INT_MAX ? 0 : ans;}
};
这个解法时间复杂度是O()其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。
但是这不是我们要学的思路,我们要探究的是另一种的解法——滑动窗口
该解法思路：
定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 nums[start] 到 nums[end] 的元素和）。
初始状态下，start 和 end 都指向下标 0，sum 的值为 0。
每一轮迭代，将 nums[end] 加到 sum，如果 sum≥s，则更新子数组的最小长度（此时子数组的长度是 end−start+1），然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum<s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。
代码如下
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;int start = 0, end = 0;int sum = 0;while (end < n) {sum += nums[end];while (sum >= s) {ans = min(ans, end - start + 1);sum -= nums[start];start++;}end++;}return ans == INT_MAX ? 0 : ans;}
};该方法时间复杂度：O(n)
2.3. 无重复字符的最长子串 - 力扣（LeetCode）
解法⼀（暴⼒求解,可以通过）：
算法思路：
枚举「从每⼀个位置」开始往后，⽆重复字符的子串可以到达什么位置。找出其中⻓度最⼤的即
可。 在往后寻找⽆重复⼦串能到达的位置时，可以用「哈希表」统计出字符出现的频次
class Solution {
public:int lengthOfLongestSubstring(string s) {int ret = 0; // 记录结果int n = s.length();// 1. 枚举从不同位置开始的最⻓重复⼦串// 枚举起始位置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;// 如果没有重复，就更新 retret = max(ret, j - i + 1);}}// 2. 返回结果return ret;}
};当然,我们知道我们想要的也不是这种解法
解法⼆（滑动窗口）：
算法思路：
研究的对象依旧是⼀段连续的区间，因此继续使⽤「滑动窗口」思想来优化。
让滑动窗口满⾜：窗口内所有元素都是不重复的。
做法：右端元素 ch 进⼊窗口的时候，哈希表统计这个字符的频次：
- 如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗口,直到 ch 这个元素的频次变为 1 ，然后再更新结果。
- 如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果
class Solution { public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 }; // 使⽤数组来模拟哈希表int left = 0, right = 0, n = s.size();int ret = 0; while(right < n){hash[s[right]]++; // 进⼊窗⼝while(hash[s[right]] > 1) // 判断hash[s[left++]]--; // 出窗⼝ret = max(ret, right - left + 1); // 更新结果right++; // 让下⼀个元素进⼊窗⼝}return ret;} };3.1004. 最大连续1的个数 III - 力扣（LeetCode）
思路与算法
不要去想怎么翻转，不要把问题想的很复杂，这道题的结果⽆⾮就是⼀段连续的 1 中间塞了 k
个 0 嘛。
因此，我们可以把问题转化成：求数组中⼀段最⻓的连续区间，要求这段区间内 0 的个数不超
过 k 个
代码如下
class Solution
{
public:int longestOnes(vector<int>& nums, int k) {int ret = 0;for(int left = 0, right = 0, zero = 0; right < nums.size(); right++){if(nums[right] == 0) zero++; // 进窗⼝while(zero > k) // 判断if(nums[left++] == 0) zero--; // 出窗⼝ret = max(ret, right - left + 1); // 更新结果}return ret;}
};是不是很简单呢?