双指针

核心思想

双指针是一种思想，它可以用来优化暴力

通过两个指针维护一些具有单调性，可快速增删的区间信息，将时间复杂度大幅度降低

例如快速排序使用了双指针的思想，将时间复杂度降低到了\(O(nlogn)\)

不通用模板

for (int i = 1, j=1;i<=n;i++){
    while(j<i && check(i,j)){
        j++;
    }
}

快慢指针

最长连续不重复序列

给定一长度为n的整数序列，找出最长的不包含重复的数的连续区间，输出长度

输入例
1
2
5
1 2 2 3 5
输出例
1
3

传统思想为用二重循环从头开始遍历，直到找到一个区间中间没用重复元素

### 图解

如两个指针（不是分配内存的指针）同时指向头部

i先移动，将指到的数出现次数加一，同时满足此时为一个不重复序列，更新答案i-j+1

当i移动到第二个2，记录了两次相同数字，这时i与j之间的数列不符合条件，让j移动到i处

移动后将前面的序列抛弃，且将每个数重新计数以寻找下一子序列

代码实现

// 给定一长度为n的整数序列，找出最长的不包含重复的数的连续区间，输出长度
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <utility>
#include <cstring>
#include <iomanip>
#define ios ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e5+10;
typedef pair<int,int> PII;

int n;
int a[N];
int cnt[N];

int main(){
  cin >> n;
  for (int i = 1; i <=n;i++) cin >> a[i];

  int res = 1;
  for (int i = 1, j = 1; i<=n;i++){
    cnt[a[i]]++;  // 记录序列数字出现次数
    while(cnt[a[i]]>1){  // 当发现重复数字
      cnt[a[j++]]--; // 将j从头开始移动到重复数字处，并清除之前的计数
    }
    res = max(res,i-j+1);  // 更新最大子序列长度
  }
  cout << res;
  return 0;
}

对撞指针

对撞指针的思想：左右两个指针向中间寻找知道对撞

用对撞指针实现快速排序

将数组最后一个数right作为基数key
从首元素begin开始向后寻找比key大的数，end开始向前寻找比key小的数，找到后两者交换
直到begin>=end终止遍历
将begin和最后一个数交换，此时key作为中间数，左边都比key小右边都比key大
递归对左右区间重复操作，直到剩一个元素

代码：

#include <iostream>
using namespace std;

// 分区函数
int PartSort1(int* a, int begin, int end) {
    int keyIndex = begin;
    while (begin < end) {
        while (begin < end && a[end] >= a[keyIndex]) end--; // 注意取等
        while (begin < end && a[begin] <= a[keyIndex]) begin++; // 注意取等
        swap(a[begin], a[end]);
    }
    swap(a[begin], a[keyIndex]);
    return begin;
}

// 递归快速排序
void QuickSort(int* a, int begin, int end) {
    if (begin >= end) return; // 递归终止条件
    int pivot = PartSort1(a, begin, end); // 分区
    QuickSort(a, begin, pivot - 1); // 左部分递归
    QuickSort(a, pivot + 1, end);  // 右部分递归
}

int main() {
    int arr[] = {9, 3, 7, 6, 2, 8, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    QuickSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

红魔咖啡馆

【算法】双指针

双指针

核心思想

不通用模板

快慢指针

最长连续不重复序列

代码实现

对撞指针