滑动窗口
代码框架（借鉴力扣大佬的labuladong）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

1相差不超过k的最多数

给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过,问最多能选择多少个数？
输入描述:

1
2
第一行输入两个正整数 n和k
第二行输入 n个正整数 ai用空格隔开，表示这个数组

输出描述:

1
2
3
4
一个正整数，代表能选的最多数量
数据范围：
1≤n≤2×10^5
1≤k,ai≤10^9

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    vector<long long> arr(n);
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr.begin(),arr.end());
    int max_length=0,left=0;
    for(int right=0;right<n;right++){
        while((arr[right]-arr[left])>k){
            left++;
        }
        max_length=max(max_length,right-left+1);
    }
    cout<<max_length<<endl;
    return 0;
}

2长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 找出该数组中满足其总和大于等于 target 的长度最小的 子数组
[numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度 如果不存在符合条件的子数组,返回 0

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum=0,max_length=nums.size()+1,left=0;
        for(int right=0;right<nums.size();right++){
            sum+=nums[right];
            while(sum>=target){
                max_length=min(max_length,right-left+1);
                sum-=nums[left++];
            }
        }
        return max_length<=nums.size()?max_length:0;
    }
};

3无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.length(),ans=0,left=0;
        unordered_set<char> window;
        for(int right=0;right<n;right++){
            char c=s[right];
            while(window.count(c)){
                window.erase(s[left++]);
            }
            window.insert(c);
            ans=max(ans,right-left+1);
        }
        return ans;
    }
};

4乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1) return 0;
        int n=nums.size(),ans=0,prod=1,left=0;
        for(int right=0;right<n;right++){
            prod*=nums[right];
            while(prod>=k){
                prod/=nums[left++];
            }
            ans+=right-left+1;
        }
        return ans;
    }
};

5包括不超过两种字符的最长字串

描述
给定一个长度为 n 的字符串，找出最多包含两种字符的最长子串 t ，返回这个最长的长度。
数据范围： 1≤n≤10^5 字符串种仅包含小写英文字母

输入描述：
仅一行，输入一个仅包含小写英文字母的字符串

输出描述：
输出最长子串的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    string str;
    cin>>str;
    int n=str.length();
    unordered_map<char, int> map;
    int ans=0,left=0;
    for(int right=0;right<n;right++){
        map[str[right]]++;
        while(map.size()>2){
            map[str[left]]--;
            if(map[str[left]]==0){
                map.erase(str[left]);
            }
            left++;
        }
        ans=max(ans,right-left+1);
    }
    cout<<ans<<endl;
    return 0;
}

6DNA序列

描述

一个 DNA 序列由 A/C/G/T 四个字母的排列组合组成。
G 和 C 的比例（定义为 GC-Ratio ）是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目（也就是序列长度）。
在基因工程中，这个比例非常重要。因为高的 GC-Ratio 可能是基因的起始点。

给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。
DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等

数据范围：字符串长度满足 1≤n≤1000 ，输入的字符串只包含 A/C/G/T 字母

输入描述：

输入一个string型基因序列，和int型子串的长度

输出描述：

找出GC比例最高的子串,如果有多个则输出第一个的子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
string findHighestGCRatioSubstr(string str,int k){
    int n = str.size();
    int maxGCRatio = 0;
    int currentGCRatio = 0;
    string result="";
    //初始化窗口
    for(int i=0;i<k;i++){
        if(str[i]=='G'||str[i]=='C') currentGCRatio++;
    }
    maxGCRatio=currentGCRatio;
    result=str.substr(0,k);
    for(int right=k;right<n;right++){
        if(str[right]=='G'||str[right]=='C') currentGCRatio++;
        if(str[right-k]=='G'||str[right-k]=='C') currentGCRatio--;
        if(currentGCRatio>maxGCRatio){
            maxGCRatio=currentGCRatio;
            result=str.substr(right-k+1,k);
        }
    }
    return result;
}

int main() {
    string str;
    int k;
    cin>>str>>k;
    cout<<findHighestGCRatioSubstr(str, k)<<endl;
    return 0;
}

7连续最大和

描述

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

输入描述：

输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述：

所有连续子数组中和最大的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int sum=arr[0],ans=arr[0];
    for(int right=1;right<n;right++){
        sum=max(arr[right],sum+arr[right]);
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}