双指针算法

其实快排和归并就用到了双指针算法！

思想与用途：双指针算法可以将的复杂度优化成。每一个指针总共移动的次数是不超过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表来做