双指针的题目往往是看起来需要O（n),我们一般枚举一个指针，然后我们发现另一个指针不走回头路，不论是哪个方向，这样我们的时间复杂度就是O(n).
从例题来看:

给定一个字符串，我们希望找到最短长度区间能包含所有字母类型。

###核心：对于左端点固定的时候，我们找到最小的r，然后我们考虑i右移动一位，这时候我们的j是一定不会回头的，因为不回头，都已经少了一个字母且当前假设已经不包含所有字母了，。
所以i和j都是单调移动的
https://codeforces.com/contest/701/problem/C

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Problem: C. They Are Everywhere
// Contest: Codeforces - Codeforces Round 364 (Div. 2)
// URL: https://codeforces.com/problemset/problem/701/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define debug1(x) cerr<<x<<" "
#define  debug2(x) cerr<<x<<endl
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];

void solve(){
	cin>>n;
	string str;cin>>str;
	set<int>s;
	for(int i=0;i<n;i++){
		s.insert(str[i]);
	}
	int m=s.size();
	map<char,int >ans;int res=inf;
	int j=0;
	for(int i=0;i<n;i++){
		while(j<n&&ans.size()<m){
			ans[str[j]]++;
			j++;
			}
			//cerr<<i<<" "<<j<<endl;
		if(ans.size()==m)res=min(res,j-i);
		ans[str[i]]--;
		if(ans[str[i]]==0)ans.erase(str[i]);
	}
	cout<<res;
}
int main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}

例题2

https://ac.nowcoder.com/acm/problem/269221

题意：需要在有序数组中找到最长区间满足区间极差小于等于m

做法：我们考虑枚举左端点，那么当左端点增大，右端点一定只能不动或者向右移动

  • 所以也可以双指针解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int ans=-1;
	sort(a+1,a+n+1);int j=1;
	//for(int i=1;i<=n;i++)cerr<<a[i]<<" ";
	//cerr<<endl;
	for(int i=1;i<=n;i++){
		while(j+1<=n&&a[j+1]-a[i]<=m)j++;
		//cerr<<i<<" "<<j<<endl;
		ans=max(ans,j-i+1);
	}
	double res=1.0*ans/(double)n;
	baoliu(res,6);
}

本题为easy版本，和hard版本的唯一区别是aia_i保证是正整数**！**

小红拿到了一个数组，她想知道，有多少非空区间满足区间所有元素之和不小于kk？

由于这个版本a[i]都是正整数，我们直接前缀和转化以后，等价于前缀和数组视角下的上一题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
	int k;cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
int j=1;
int ans=0;
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++){
	while(j<=n&&s[j]-s[i-1]<k)j++;
	//cerr<<i<<" "<<j<<endl;
	ans+=n-j+1;
	
}
cout<<ans;
}

hard版本：带负数情况

  • 我们需要找到大于a[i]+k的数a[j]且j>i.
  • 由于存在负环没有单调性，我们只能用解决逆序对的方法：离散化权值树状数组
  • 我们要求的是后缀，所以还要倒着求，我们枚举的是左端点

离散化过程明显不熟，下次看到的时候一定要刻意练习

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// Problem: 小红统计区间（hard）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/73239/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define debug1(x) cerr<<x<<" "
#define  debug2(x) cerr<<x<<endl
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
vector<int>lan;
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
/*
T{}是一种初始化T类型对象的方式，它使用了花括号初始化列表进行数值初始化。
对于大多数内置数据类型（如整数、浮点数），这将初始化为0。
*/

    }
    
    void add(int x, const T &v) {
        for (int i = x; i <=n-1; i += i & -i) {
            a[i] = a[i] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {//要传入l-1
    //待优化：直接给个vector记录前缀和
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {//寻找最后一个使得前缀和小于等于 k 的位置。
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n-1); i; i /= 2) {//GCC
            if (x + i <= n-1 && cur + a[x + i] <= k) {
                x += i;
                cur = cur + a[x];
            }
        }
        return x;
    }
};

void discrete()
{
    sort(lan.begin(), lan.end());   //排序
    lan.erase(unique(lan.begin(), lan.end()), lan.end());   //去重
}

//查询
int find(int x)
{
 return lower_bound(lan.begin(), lan.end(), x)-lan.begin()+1;  //返回所查询的数据的下标
}
//为了迎合这大于等于第一个数的离散数，我们希望我们在查询的时候
//能得到查找一系列大于什么的数，s[j]>=s[i]+k
//老是糊涂的一点是，我们枚举的l-1，s[r]-s[l-1];
//所以我们枚举的时候是0-n-1，我们需要不断查询后缀和，如果正着做
//我们会不知道后面到底有多少个数，因为离散化vector只有大小关系
//原来的位置关系并不知道。所以我们从后往前扫，首先记得将s[n]加入到
//树状数组中去，因为枚举的时候是0-n-1
void solve(){
	int k;cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
		lan.push_back(a[i]);
	}
	Fenwick<int>c(n+1);
	discrete();
	//for(auto x:lan)cerr<<x<<" ";
	//cerr<<endl;
	int ans=0;
	int tt=find(a[n]);
	c.add(tt,1);
	for(int i=n-1;i>=0;i--){
		int pos=1;
	 pos=find(a[i]+k);
	// cerr<<a[i]<<" "<<a[i]+k<<" "<<pos<<endl;
		if(pos!=lan.size()+1)ans+=c.rangeSum(pos-1,n);
		//cerr<<c.rangeSum(pos-1,n)<<endl;
		int tmp=find(a[i]);
		c.add(tmp,1);
	}
	cout<<ans<<endl;
}
signed main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}