滑动窗口（一）

Leetcode209. 长度最小的子数组

题目

Leetcode209. 长度最小的子数组

解法一(暴力求解)（超时）

暴力枚举出所有子数组的和 O(n^2);

代码

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int res = INT_MAX;// 记录答案for(int i = 0; i < n; i++){int sum = 0;for(int j = i; j < n; j++){sum += nums[j];if(sum >= target){res = min(res, j - i + 1);break;}}}return res == INT_MAX ? 0 : res;}
};

解法二（滑动窗口）

开始将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：

• 如果窗⼝内元素之和⼤于等于target ：更新结果，并且将左端元素划出去的同时继续判
  断是否满⾜条件并更新结果（因为左端元素可能很小，划出去之后依旧满⾜条件）
• 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝。

O(N^2)

代码

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int res = INT_MAX;int sum = 0;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right];//进窗口while(sum >= target)//判断{res = min(res, right - left + 1);//更新结果sum -= nums[left++];//出窗口}}return res == INT_MAX? 0:res;}};

Leetcode3. 无重复字符的最长子串

题目

Leetcode3. 无重复字符的最长子串

解法一（暴力求解）

从每一个字母开始向后枚举无重复字符的字串最大的长度
利用哈希表来统计每一个字符出现的次数

代码

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int res = 0;int n = s.size();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;}res = max(res, j - i + 1);}}return res;}
};

解法二（滑动窗口）

右端元素 ch 进⼊窗⼝的时候，哈希表统计这个字符的频次：

• 如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，
  直到 ch 这个元素的频次变为 1 ，然后再更新结果。
• 如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果。
  代码

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int res = 0;int n = s.size();int hash[128] = {0};//利用数组模拟哈希统计字符出现次数for(int left = 0, right = 0; right < n; right++){hash[s[right]]++;//进窗口while(hash[s[right]] > 1)//判断{hash[s[left]]--;//出窗口left++;}res = max(res, right - left + 1);// 更新结果}return res;}
};

Leetcode1004. 最大连续1的个数 III

题目

Leetcode1004. 最大连续1的个数 III

解法（滑动窗口）

我们发现一会从左边开始减、一会从右边开始减，这样做起来十分麻烦，因为我们不确定从哪边开始，所以我们不要想着如何反转，而是一段连续的1中间有k个0。
因此，我们将题目转化为了求一段最长连续区间，要求其中的0不能超过k

代码

class Solution 
{
public:int longestOnes(vector<int>& nums, int k) {int res = 0;int zero = 0;//统计0的个数for(int left = 0, right = 0; right < nums.size(); right++){if(nums[right] == 0) zero++;//进窗口while(zero > k)//判断{if(nums[left++] == 0) zero--;//出窗口}res = max(res, right - left + 1);//更新结果}return res;}
};