又是一个降低时间复杂度的妙妙道具
比方说，原来的暴力朴素代码
for (i = 0; i < n; i ++ )
{
for (int j = 0; j < n; j ++ )
{
//具体逻辑
}
}
很显然时间复杂度为O(n2)，但这样肥肠容易TLE。
于是乎，就有了聪明的人想了一个办法：
for (i = 0, j = 0; i < n; i ++ )
{
while (j 满足 限制条件 && check(i, j)) j ++ ;
//具体逻辑
}虽然这样看着还是两层循环，但实际上最多只会执行2n次。
这意味着时间复杂度降低到了O(n)
好吧，这样讲还是有点抽象，让我们结合一下具体的例子
str.replace(” “,”\n”)
因为不知道如何给这个问题起名字，所以直接用python的语言表示了。很显然这个问题用python只要如上一行代码就可以解决了。现在让我们看看如何用C++并使用双指针算法解决。
*虽然可以用 while(cin >> s) ，但这里学习的是双指针算法所以不予采纳。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s; getline(cin, s);
int n = s.size();
for (int i = 0; i < n; i ++ )
{
int j = i;
while (j < n && s[j] != ' ') j ++ ;
for (int k = i; k < j; k ++ ) cout << s[k];
cout << '\n';
i = j;
}
return 0;
}先贴代码
此处先使用getline保证空格能被存入字符串s中。然后我们看一下双指针代码：
- 指针 i 负责控制当前的首字母
- 指针 j 负责往后推，直到出现空格为止
- 出现空格时，以 j 为下标的元素为空格（下标为 j – 1 时执行的 j ++ 使其为空格）
- 通过 k 输出空格之前的所有元素
- 更新 i 到 j ， 之后循环的 i ++ 会让新的下标从空格后的第一个元素开始计算
好的，第一个简单而便于理解的双指针算法就完成了
最长连续不重复子序列
现在我们来看一道例题，求最长连续不重复子序列的长度
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j <= i; j ++ )
{
if (check(j, i))
{
ans = max(ans, j - i + 1);
}
}
}先看暴力算法，对于每一个右端点（指针 i 控制），枚举最远的左端点（指针 j 控制）在什么位置，时间复杂度为O(n2)
for (int i = 0, j = 0; i < n; i ++ )
{
while (j <= i && check(i, j)) j ++ ;
ans = max(ans, i - j + 1);
}再看一下双指针算法。仍然以 i 控制右侧的指针，以 j 控制左边的指针。我们要先证明一下，当 i 往右走的时候， j 不可能往左走。
证明：
假设 j 可以往左走， 则往左走了以后的 j’ 和往右走的 i’ 间没有重复元素
所以没有走过的 i 能对应走过以后的 j’
因此，j 的值应该为 j – 1，j 无法到达当前的位置，矛盾
check函数可以通过map标记实现
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n; cin >> n;
vector<int> a(n);
map<int, int> mp;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int ans = 0;
for (int i = 0, j = 0; i < n; i ++ )
{
mp[a[i]] ++ ; // 先把右边的加上
while (mp[a[i]] > 1)
{
mp[a[j]] -- ; // 有重复把左边的扔掉，扔到不重复为止
j ++ ;
}
ans = max(ans, i - j + 1);
}
cout << ans << '\n';
return 0;
}mp记录的是元素 a[i] 出现的次数。一旦 a[i] 出现的次数大于一次，就说明有重复元素。有重复元素就把左边的元素扔掉，扔到不重复为止。
可以AC最长连续不重复子序列
习题记录
1.数组元素的目标和
题目说明见超链接
版本一：暴力O(n2)，注定TLE
for (int i = 0; i < n && a[i] < x; i ++ )
{
for (int j = 0; j < m && b[j] < x; j ++ )
{
if (a[i] + b[j] == x)
{
cout << i << ' ' << j << '\n';
return 0;
}
}
}版本二：尝试双指针，调半天没调出来，希望后续哪天能调出来
for (int i = 0, j = 0; i < n && (i + 1 < m ? a[i + 1] < x : a[i] < x); i ++ )
{
while (j < m && (j + 1 < m ? b[j + 1] < x : b[j] < x) && a[i] + b[j] < x) j ++ ;
cerr << i << ' ' << j << ':' << a[i] << ' ' << a[j] << '\n';
if (a[i] + b[j] == x)
{
cout << i << ' ' << j << '\n';
return 0;
}
}版本三：STL大法之lower_bound，复杂度正确，算法正确，但作为双指针的题目总感觉差点什么，可能是想让我写二分？总之代码先贴出来再说
for (int i = 0; i < n; i ++ )
{
int j = lower_bound(b.begin(), b.end(), x - a[i]) - b.begin();
if (a[i] + b[j] == x)
{
cout << i << ' ' << j << '\n';
return 0;
}
}版本四：补充一版被GPT调教过的双指针
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m, x;
cin >> n >> m >> x;
vector<int> A(n), B(m);
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++)
{
// check(i, j)：A[i] + B[j] > x
while (j >= 0 && A[i] + B[j] > x)
j--;
if (j >= 0 && A[i] + B[j] == x)
{
cout << i << " " << j << endl;
break;
}
}
return 0;
}正确性证明
a数组b数组都严格单调递增
a数组从左往右遍历，b数组从右往左遍历。
所以 a[i] 在不断增大，b[j]在不断减小
所以，若a[i] + b[j]大于x，则a[i] + b[j + 1]一定大于x
所以 j — 是严格的
2.判断子序列
依旧题目见超链接。很朴素的一个双指针，但是依旧WA了好多发才过。对于算法不熟练导致的后果。
代码先贴出来
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m; cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = 0; i < m; i ++ ) cin >> b[i];
int cnt = 0;
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < m && a[i] != b[j]) j ++ ;
if (j >= m) break;
// cerr << j << '\n';
cnt ++ ; j ++ ;
}
cout << (cnt == n ? "Yes\n" : "No\n");
return 0;
}对 a 中每一项逐个判断是否在 b 中出现。因为要求按原顺序的子序列，所以 j 不用重置为0，保存当前值即可。
写了好久的博客，终于把这一篇写完了。算法还是不太熟悉，都WA了好多发，要多练练了
评论（0）
暂无评论