双指针也不一定是两个指针也可以是多个指针同时前进
主要是一种思想 将O(n^2)时间复杂度优化为O(n)
#核心模板
for(int i = 0,j = 0;i < n;i++){

    while(j <= i && check(i,j)) j++;
    ...
}

1.完全二叉树的权值

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？

如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅AN。

输出格式
输出一个整数代表答案。

数据范围
1≤N≤105,
−105≤Ai≤105
输入样例：
7
1 6 5 4 3 2 1
输出样例：
2

#include<iostream>

using namespace std;

typedef long long LL;

const int N=1e5 + 10;

int a[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];

    LL maxl = -0x3f3f3f;
    int depth = 1;

    for(int d = 1,i = 1;i <= n;i*=2,d++){
        LL s = 0;
        for(int j = i;j < i + (1 << (d-1)) && j <= n;j++) #每一层的范围内进行操作
            s+=a[j];
        if(s > maxl){
            maxl = max(s,maxl);
            depth = d; 
        }
    }

    cout << depth << endl;

    return 0;
}

2.日志统计

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式
第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts 和 id。

输出格式
按从小到大的顺序输出热帖 id。

每个 id 占一行。

数据范围
1≤K≤N≤105,
0≤ts,id≤105,
1≤D≤10000
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例：
1
3

#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int,int> PII;

#define x first
#define y second

const int N = 1e5 + 10;

PII q[N];
int cnt[N];
bool st[N];//热度状态
int main(){
    int n,d,k;
    cin >> n >> d >> k;

    for(int i = 0;i < n;i++) cin >> q[i].x >> q[i].y;

    sort(q,q+n);

    for(int i = 0,j = 0;i < n;i++){
        cnt[q[i].y]++;
        while(j <= i && q[i].x - q[j].x >= d){
            cnt[q[j].y] --;
            j++;
        }
        if(cnt[q[i].y] >= k) st[q[i].y] = true;
    }

    for(int i = 0;i <= N;i++)
        if(st[i])
            cout << i << endl;

            return 0;

}

3.最长连续不重复子序列

给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续区间，输出它的长度。

输入格式
第一行包含整数n。

第二行包含n个整数（均在0~100000范围内），表示整数序列。

输出格式
共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。

数据范围
1≤n≤100000
输入样例：
5
1 2 2 3 5
输出样例：
3

/*core:
    1.i 在 右边,j 在左边
    2.while 出口在于 没有两个重复元素的断掉循环 也就是 s[a[i]] > 1
*/
#include<iostream>

using namespace std;
const int N = 1e5 + 10;
int a[N],s[N];
int main(){
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
    cin >> a[i];
    int res = 0;
    for(int i = 0,j = 0;i < n;i++){
        s[a[i]] ++;
        while(j <= i && s[a[i]] > 1) {
            s[a[j]]--;
            j++;
        }
        res = max(res,i - j + 1);//取最长
    }
    cout << res << endl;
    return 0;
}

4.数组元素的目标和

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。

数据保证有唯一解。

输入格式
第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。

第二行包含n个整数，表示数组A。

第三行包含m个整数，表示数组B。

输出格式
共一行，包含两个整数 i 和 j。

数据范围
数组长度不超过100000。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N],b[N];

int main(){
    int n,m,q;

    cin >> n >> m >> q;
    for(int i = 0;i < n;i++) cin >> a[i];
    for(int j = 0;j < m;j++) cin >> b[j];

    for(int i = 0,j = m - 1;i < n;i++){

        while(j >= 0 && a[i] + b[j] > q) j--;

        if(a[i] + b[j] == q){
            cout << i << " " << j << endl;
            break;
        }

    }

    return 0;
}