acwing算法基础之基础算法--双指针算法

1 知识点

双指针算法的核心思想：

for (int i = 0; i < n; ++i) {
	for (int j = 0; j < m; ++j) {
		//do somethings
	}
}
1
2
3
4
5

利用某些性质（比如单调性），将上面朴素算法优化到$O(N)$。

以输出空格间隔的单词这道题为例，其双指针算法实现如下，

//s为字符串，它由一系列空格隔开的单词组成
//输出每个单词组成的字符串向量words
int n = s.size();
vector<string> words;
for (int i = 0; i < n; ++i) {
	int j = i;
	while (j < n && s[j] != ' ') {
		j++;
	}
	string word;
	for (int k = i; k < j; ++k) {
		word += s[k];
	}
	words.emplace_back(word);
	i = j; //更新i
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题目样例：求数组a中最长的不含重复元素的连续区间长度，

//输入数组a
//res为最终答案
int n = a.size();
unordered_map<int, int> cnt;
int res = 0; //最终答案
for (int i = 0, j = 0; i < n; ++i) {
	cnt[a[i]]++;
	while (cnt[a[i]] > 1) {
		cnt[a[j]]--;
		j++;
	}
	res = max(res, i - j + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2 模板

for (int i = 0, j = 0; i < n; ++i) {
	while (j <= i && check(j,i)) {
		j++;
	}
	//每道题目的具体逻辑，即业务逻辑
}
1
2
3
4
5
6