LeetCode75| 滑动窗口

目录

643 子数组最大平均数 |

1456 定长子串中元音的最大数目

1004 最大连续1的个数 |||

1493 删掉一个元素以后全为1的最长子数组

---

643 子数组最大平均数 |

class Solution {
public:double findMaxAverage(vector<int>& nums, int k) {double sum = 0;double res = 0;for(int i = 0;i < k;i++)sum += nums[i];res = sum / k;int l = 0,r = k;for(;r < nums.size();){sum += nums[r++];sum -= nums[l++];res = max(res,sum / k);}return res;}
};

时间复杂度O(n)

空间复杂度O(1)

1456 定长子串中元音的最大数目

class Solution {
public:bool isVowel(char ch){return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';}int maxVowels(string s, int k) {int res = 0;for(int i = 0;i < k;i++){res += isVowel(s[i]);}     int temp = res;for(int i = k;i < s.size();i++){temp += isVowel(s[i]) - isVowel(s[i - k]);res = max(res,temp);}return res;}
};

时间复杂度O(n)

空间复杂度O(1)

1004 最大连续1的个数 |||

在确保区间内0的总数小于k的情况下统计1的数量 

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int res = 0,sum = 0;for(int r = 0,l = 0;r < nums.size();r++){if(!nums[r])sum++;while(sum > k)if(!nums[l++])sum--; res = max(r - l +1,res);}return res;}
};

时间复杂度O(n)

空间复杂度O(1)

1493 删掉一个元素以后全为1的最长子数组

与1004 最大连续1的个数 |||思路相同 

class Solution {
public:int longestSubarray(vector<int>& nums) {int res = 0,sum = 0;for(int r = 0,l = 0;r < nums.size();r++){if(!nums[r])sum++;while(sum > 1){if(!nums[l++]){sum--;}}res = max(res,r - l);//注意题意，需要删除一个元素，这里不加1}return res;}
};

时间复杂度O(n)

空间复杂度O(1)