[滑动窗口] (一) LeetCode 209. 长度最小的子数组 和 LCR 016.无重复字符的最长子串
[滑动窗口] (一) LeetCode 209. 长度最小的子数组 和 LCR 016.无重复字符的最长子串
文章目录
- [滑动窗口] (一) LeetCode 209. 长度最小的子数组 和 LCR 016.无重复字符的最长子串
- 什么是滑动窗口
- 长度最小的子数组
- 题目解析
- 解题思路
- 代码实现
- 总结
- 无重复字符的最长子串
- 题目解析
- 解题思路
- 代码实现
- 总结
什么是滑动窗口
滑动窗口并不是真的创建出一个数组，而是利用一个left“指针”和right“指针”，让它们在原数组之间的区间来模拟出一个类似窗口的"数组"，一般由right向右移动扩大窗口大小，直到不满足要求后，再让left向右移动。
这就是模拟出一个滑动窗口。
长度最小的子数组
209. 长度最小的子数组
题目解析
(1) 含有正整数的nums和一个正整数target
(2) 找出一个连续子数组的总和大于等于target
解题思路
通过题目解析，我们确定了这道题的解法。
解法：滑动窗口
构建一个left指针， 一个right指针。让他们之间的区间模拟，我们想要的小于target的一一个连续子数组。
由right来进窗口，left负责出窗口。在每次出窗口前更新结果。
示例1：
看到这里，大家可以先去实现代码，再看下面的内容。
代码实现
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, ret = INT_MAX;for(int left = 0, right = 0; right < nums.size(); right++){//进窗口sum += nums[right];//判断while(sum >= target){//更新结果ret = min(ret, right - left + 1);//出窗口sum -= nums[left++];}}return ret == INT_MAX ? 0 : ret;}
};
总结
细节1：ret赋值为INT_MAX，方便最后两数取小。
细节2：返回时判断，ret是否为INT_MAX，否则返回0
无重复字符的最长子串
LCR 016. 无重复字符的最长子串
题目解析
(1) 从字符串中找出一个子字符串
(2) 子字符串的要求：最长且不能有字母重复
解题思路
从题目分析得出，我们这道题可以使用滑动窗口+哈希的方法
解法：滑动窗口+哈希
定义一个left，right指针，right负责进窗口，left负责出窗口，哈希表进行判断子串是否重复。
当重复时，left不断出窗口直到hash[s[right]]不大于1。在每次不重复时更新结果。
示例1：
看到这里，大家可以先去实现代码，再看下面的内容。
代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.size() == 0) return 0;int ret = 0;int hash[128] = {0};for(int left = 0, right = 0; right < s.size(); right++){//进窗口hash[s[right]]++;//判断while(hash[s[right]] > 1){//出窗口hash[s[left++]]--;}//更新结果ret = max(ret, right - left + 1);}return ret;}
};
总结
细节1：每次进入一个字符就需要更新一次结果。
细节2：字符串为空时，返回0。