双指针算法
其实快排和归并就用到了双指针算法！
思想与用途：双指针算法可以将的复杂度优化成
。每一个指针总共移动的次数是不超过
n的，两个指针总共移动的次数不会超过2n 。非常强大好用，将暴力算法优化！
- 双指针算法的经典使用
// 分开字符串中的word 双指针做法
#include <iostream>
#include <string.h>
char str[1000];
using namespace std;
int main(){
cin.getline(str,1000); // gets从键盘中读入到str数组 gets被禁 使用cin.getline也可以
int n = strlen(str);
for(int i=0;i<n;i++){
int j = i; // 这个j指针才是具体检索单词的指针
while(j < n && str[j]!=' ')j++; // j结束的时候在' '处
for(int k=i;k<j;k++) cout << str[k];
cout << endl;
i=j; // 让i跨到目前的j处
}
return 0;
}
// 当然此题使用单指针效率也是O(n)
双指针算法的概念非常广泛
- 最长不包含重复数字连续子序列
// 1 2 2 3 4 5
// 暴力算法 核心 O(n^2)
for(int j = 0;j<n;j++){ // j是终点指针
for(int i=0;i<j;i++){
check(i,j){
res = Max(res,j-i+1);
}
}
}
// 双指针算法 O(2n)
for(int i=0;i<n;i++){
while(i < j && check(i,j)){
}
}
双指针算法都是从暴力算法改进而来，往往是找出两个指针之间的关系，从而不用全部枚举数对
往往是：暴力算法与双指针算法 第一个指针都是一样 扫一遍。双指针算法的第二个指针往往只要扫一遍，而暴力算法来回的扫若干遍
#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N],cnt[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++){
cnt[a[i]]++;
while(cnt[a[i]] == 2){ // cnt[a[i]]和cnt[a[j]]修改的是同一个值，通过cnt[a[j]]来改变cnt[a[i]]
cnt[a[j]]--;
j++;
} // 这个while是核心 结束的时候i=j(示例序列是这个)或者 i= j+1
res = max(res,i-j+1);
}
cout << res << endl;
return 0;
}
当数组比较长的话，可以用hash表来做。起到 不开数组判重的作用
双指针算法案例：
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解
// 暴力
for(int i = 0; i < m;i++){
for(int j = 0 ; j< n ;j ++){
if (A[i] + B[j] == x){
cout << i << j << endl;
break;
}
}
}
时间复杂度，由于A数组和B数组都是单调数组，因此可以通过单调性来合理的“跳”过一些比较计算，只计算有用的。这就是双指针对暴力的优化。对于本题来说具体选用双指针中的对撞指针
#include <iostream>
using namespace std;
const int N = 10e5+10;
int A[N],B[N];
int n , m ;
int x;
int main(){
scanf("%d%d%d",&n,&m,&x);
for(int i = 0;i<n;i++){
scanf("%d",&A[i]);
}
for(int j = 0;j<m;j++){
scanf("%d",&B[j]);
}
for(int i = 0,j = m-1;i<n;i++){
while(j >= 0 && A[i] + B[j] >x) j--;
if(A[i] + B[j] == x){
cout << i << " " << j<<endl;
break;
}
}
return 0;
}
本题如果没有限制解的个数是唯一的话，就不能使用双指针来优化，只能暴力。
若是两个数组是无序的话，也能做，使用hash表来做
