今天做了一份滑动窗口的专题
leecode209. 长度最小的子数组
滑动窗口呢，说白了也是双指针问题
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int front_index = 0;
int end_index = 0;
int result = 1e9;
while(end_index < nums.size() && front_index <= end_index){
if(sum(nums, front_index,end_index) < target){
end_index++;
}
else if(sum(nums, front_index, end_index) >= target){
result = min(result, end_index - front_index + 1);
front_index++;
}
}
if(result == 1e9) return 0;
else return result;
}
int sum(vector<int>& nums, int begin, int end){
int sum = 0;
for(int i = begin; i <= end; i++){
sum+=nums[i];
}
return sum;
}
};
下面的方法省掉了sum函数。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = 1e9;
int sublength = 0;
int i = 0;
int sum = 0;
//初始化后指针j
for(int j = 0; j < nums.size(); j++){
sum+=nums[j];
//这里要注意，只有sum>=target的时候才会执行，如果一直不执行，result恒等于1e9，
//所以最后出结果的时候要进行判断
while(sum >= target){
sublength = j - i + 1;
result = min(sublength, result);
sum-=nums[i++];
}
}
return result == 1e9 ? 0 : result;
}
};
leecode643. 子数组最大平均数 I
双指针法，直接秒杀
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double result = -1e9; // 因为有负数，所以这么写
//平均值最大，意味着和最大
double average = 0;
double sum = 0;
int i = 0;
for(int j = 0; j < nums.size(); j++){
sum+=nums[j];
while(j-i+1==k){
average = sum/(j-i+1);
result = max(result, average);
sum-=nums[i++];
}
}
return result;
}
};
leecode1695. 删除子数组的最大得分
class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
int l = 0;
int r = 0;
int sum = 0;
int ans = 0;
map<int,int> cnt;
for(r; r < nums.size(); r++){
cnt[nums[r]]++;
//如果发现重复元素,就把做指针想右边移动，因为重复的数字一定是新进窗口的数字
//所以判断cnt[nums[r]]是否大于1
while(cnt[nums[r]] > 1){
cnt[nums[l]]--;
sum -= nums[l];
l++;
}
sum += nums[r];
ans = max(ans, sum);
}
return ans;
}
};
leecode3. 无重复字符的最长子串
此题用滑动窗口也可直接秒杀
这道题目其实跟leecode3如出一辙，但是这道题我在写的时候出了点小问题,我最开始的代码如下
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int cnt[26] = {0};
int l = 0;
int r = 0;
int sub = 0;
int ans = 0;
if(s.length() == 0) return 0;
else{
for(r; r < s.length(); r++){
cnt[s[r]-'a']++;
while(cnt[s[r] - 'a'] > 1){
cnt[s[l]-'a']--;
l++;
sub = r - l + 1;
}
sub = r - l + 1;
ans = max(sub, ans);
}
return ans;
}
}
};
但是这种代码会报错，但输入是" “的时候，因为我只判断了当字符串长度为0时的情况，如果输入是” "的时候，cnt数组的索引会为负数。会出现如下错误
所以为了防止负数索引的出现，我建议使用map一一映射来存储26个字母出现的顺序
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> cnt;
int l = 0;
int r = 0;
int sub = 0;
int ans = 0;
if(s.length() == 0 || s.empty()) return 0;
else{
for(r; r < s.length(); r++){
cnt[s[r]]++;
while(cnt[s[r]] > 1){
cnt[s[l]]--;
l++;
sub = r - l + 1;
}
sub = r - l + 1;
ans = max(sub, ans);
}
return ans;
}
}
};
但是我们已经知道测试用例里用的ascll码中最小的为char = ’ '。所以我们可以采用以下索引，这样就不会出现错误
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int cnt[100] = {0};
int l = 0;
int r = 0;
int sub = 0;
int ans = 0;
if(s.length() == 0 || s.empty()) return 0;
else{
for(r; r < s.length(); r++){
cnt[s[r]-' ']++;
while(cnt[s[r]-' '] > 1){
cnt[s[l]-' ']--;
l++;
sub = r - l + 1;
}
sub = r - l + 1;
ans = max(sub, ans);
}
return ans;
}
}
};
leecode159. 至多包含两个不同字符的最长子串
同样使用双指针算法，注意这里，map和unordered_map的时间复杂度并不一样。map是logn，unordered_map则是1，所以键值对储存可以使用unordered_map
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int l = 0;
int r = 0;
int sub = 0;
int ans = 0;
unordered_map<char, int> cnt;
for(r; r < s.size(); r++){
cnt[s[r]]++;
//至多包含两个，那就是说当字符串中有三个一样的元素时候，left指针就要向左移动
while(cnt.size() >= 3){
cnt[s[l]]--;
if(cnt[s[l]] == 0){
cnt.erase(s[l]);
}
l++;
sub = r - l + 1;
}
sub = r - l + 1;
ans = max(sub, ans);
}
return ans;
}
};
