算法——双指针算法_双指针一层for循环一层while循环为什么可以降低时间复杂度

双指针算法

​ 双指针算法是指一切采用双指针的方式，降低原本暴力解法的时间复杂度的算法，通常双指针算法可以将暴力的 O(n^2)降低到 O(n)

​ 由于双指针算法指的是一类算法，下面我用两道题来简单解释一下

单词个数问题

​ 即查找一段字符串中，以空格为分隔的单词的个数，这道题用暴力法完全可解，外层 for 循环遍历整个字符数组，内层 for 循环检测 ' ' 字符，但是显然这种方法时间复杂度是 O(n^2)

​ 如果采用双指针算法， 外层循环用来控制遍历字符串，内层循环直接跳到 ' ' 处，记住这个单词后，直接将外层循环跳到 ' ' 的下一位继续执行，时间复杂度便为 'O(n)'

代码

#include <iostream>
#include <string>

using namespace std;

int numStr(char str[]) {
	int sum = 0;
	int l = 0, r = 0;
	int length = strlen(str);
	while (str[l]) {
		while (r <= length && str[r] != ' ')
			r++;
		for (int k = l; k < r; k++)
			cout << str[k];
		cout << endl;
		sum++;
		l = ++r;
	}
	return sum;
}

int main() {
	int sum = numStr("hello world !");
	cout << "有 " << sum << " 个单词" << endl;
	return 0;
}
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

最长连续不重复子序列问题

​ 首先，这个问题也可以使用暴力法，嵌套 for 循环，可以解决问题，但是速度慢且代码复杂

​ 采用双指针算法的思想，第一个指针持续后移，使用另一个数组统计每个数字出现的次数来控制第二个指针的移动，以此来计算不重复子序列，时间复杂度可达到 O(n)

代码

#include <iostream>
#include <Windows.h>

using namespace std;

const int N = 100010;

int a[N];
int s[N];
int n;

int main() {
	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 (s[a[i]] > 1) {
			s[a[j]]--;
			j++;
		}
		res = max(res, i - j + 1);
	}
	cout << res << endl;	
	return 0;
}
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

归并排序

​ 另外归并排序也是双指针算法的一个实例，归并排序在我之前的博客有讲过，链接是：归并排序讲解