综述

主要是双指针和滑动指针技巧

双指针

双指针一般用于序列问题，其分配两个指针来完成算法任务，可将问题优化为线性复杂度

常见场景及应用如下

• 两边向内型
  ①快速排序的前后指针互换
  ②两头指针内夹反转序列
  ③指针位置限定排序序列大小关系
• 同向异行型
  ①慢指针等待快指针结果
  ②步长不同的双指针找分点
  ②步长不同的双指针判环
• 保持一致型
  ①序列一一比对
  ②归并排序的双指针筛数
  ③指针用来抵偿达到某种一致

PAT-A1085 排序数组连续序列

PAT-A1089

PAT-A1029 寻找中间数

最简单的做法是把两个序列读入同一个vector，调sort()函数，索引$\scriptsize \lfloor N/2\rfloor $即可，复杂度 $\scriptsize O(nlogn)$
鉴于本题样例规模 $\scriptsize \sim 10^5$，考虑类似归并有序序列的 $\scriptsize O(n)$ 双指针方法
基于有序列表的性质，还可用二分方法优化至 $\scriptsize O(logn)$，将在二分文章中讲解

---

(ˉ﹃ˉ) Q：两个数组都可能会优先被遍历完末尾，这种情况怎么处理？

(′～`●) A：任一指针先到达末尾，后续都只能从另一序列继续递增。基于此想法，优先处理到达末尾S[n-1]的情况：排除到达末尾情况，此时两指针的递增保证在合法范围，就可以类似合并有序序列操作啦

(?∀?) Q：如果p1,p2初始化为0，假定S1<S2，在刚刚遍历完毕S1从S2开始时，p2++会多加一次，不加又无法向后继续怎么办？

(-ω- ) A：呼~动下小脑筋，让指针从 -1开始递增 ，是不是就能统一啦？相应地，在比较元素时，必须比较的是 S1[p1+1]和S2[p2+1]。当然也有个指针从0开始的好方法，就是让结尾S[n]=MAX_INT，这样也达到了统一

(-_-。)??? Q：怎么判定算法结束？怎么判定中位数最后是S1[p1]还是S2[p2]？

(`･ω･′)ゞ A：循环次数实际就是指针移动的次数，将两个序列看为一个序列，中位数下标为 $\scriptsize (\frac{N-1}{2})=(\frac{n1+n2-1}{2})$，指针从 $\scriptsize (-1)→(\frac{n1 + n2 – 1}{2})$ 得循环次数为 $\scriptsize \frac{n1 + n2 + 1}{2}$；最后一次修改后的指针必然是所求中位数位置，每次修改指针使用变量保存起来就OK了。使用0开始方案可以减少访存：中位数实际是结束时p1和p2所指的元素中更小的那个

(●?ω?●) Q：题目加黑的long int，我要设置long类型吗？

(◍’౪`◍)ﾉﾞ A：g++中long int与int同被编译为4B=32bit，int即可

---

#include <iostream>
using namespace std;

const int maxn = 200001;
int s1[maxn], s2[maxn];

int main() {
    int n1, n2;
    scanf("%d", &n1);
    for (int i = 0; i < n1; i++)
        scanf("%d", &s1[i]);
    scanf("%d", &n2);
    for (int i = 0; i < n2; i++)
        scanf("%d", &s2[i]);

    int p1 = -1, p2 = -1, cnt = (n1 + n2 + 1) / 2, m;
    while (cnt--) {
        if (p1 == n1 - 1) { m = s2[++p2]; continue; }
        if (p2 == n2 - 1) { m = s1[++p1]; continue; }
        if (s1[p1 + 1] < s2[p2 + 1]) m = s1[++p1];
        else m = s2[++p2];
    }
    printf("%d\n", m);
    return 0;
}

PAT-A1048 排序数组连续和问题

关于此问题及变式解法如下

和为S的两数
给定两指针：$\scriptsize small$ 从0开始后向遍历，$\scriptsize large$ 从N-1开始前向遍历
① 先卡右边界确定最大能取的数：此时 $\scriptsize small$ 是最小的，和 $\scriptsize sum \gt small+large$，一定是 $\scriptsize large$ 过大要向小调整，否则无解。
② 再卡左边界最小可取的数：此时 $\scriptsize large$ 已经是最大了，如果这个时候 $\scriptsize sum \lt small+large$，说明 $\scriptsize small$ 还不够大要向大调整，否则无解。
③ $\scriptsize sum = small+large$，此时找到最小 $\scriptsize small$ 和最大 $\scriptsize large$ 的解，若要寻找所有解，只可能在范围 $\scriptsize [small+1,large-1] 中$

连续和S的子序列
思想同上
$\scriptsize \sum\limits_{i=small}^{large}a[i] \gt S$，large–，
$\scriptsize \sum\limits_{i=small}^{large}a[i] \lt S$，large++
$\scriptsize \sum\limits_{i=small}^{large}a[i] == S$，small++，large–

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100001;
int coins[maxn];

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    memset(coins, 0, sizeof(coins));
    for (int i = 0; i < N; i++)
        scanf("%d", &coins[i]);

    sort(coins, coins + N);
    int small = 0, large = N - 1;
    while (small < large) {
        if (coins[small] + coins[large] > M)
            large--;
        else if (coins[small] + coins[large] < M)
            small++;
        else {
            printf("%d %d\n", coins[small], coins[large]);
            return 0;
        }
    }

    printf("No Solution\n");
    return 0;
}

滑动指针

滑动指针的思想是不计算具体值，只给边界并按照一定规律移动

PAT-A1105 螺旋矩阵

确定螺旋方向顺序是“右下左上”：
实现① 左右加减col，上下加减row
实现② 上下左右记入数组 $\scriptsize D=[[0,1],[1,0],[0,-1],[-1,0]]$

确定何时换方向：每检测到边界换下一方向
实现①通过while保持每个方向不变直到下一边界，防止中途更改方向
实现②检测到边界变更方向 $\scriptsize row + D[(++i)\%4][0]，col+D[(++i)\%4][1]$

关于边界的确定：
① 访问标记：不超数组边界、不覆盖已访问并标记的元素
② 逐层内夹：不超过当轮四个最外层号记录变量

---

Q：实现①我的while全写的是if，感觉没什么问题啊

A：不坚持一个方向的话，会在中途匹配到符合条件的其他方向，如下样例一直到53还运行正常，但是下一个匹配的就是20了。所以每到边界才能变更方向，变更后直到下一个边界前都要保持方向

98 95 93
42 37 81
53 20 76
58 60 76

Q：啊……我的逻辑完全没问题，但还是有测试点错误？

A：看看你的数据满不满足 $\scriptsize m\geqslant n$，题中着重要求啦。题意的最小差距是整数算数平方根，找到 $\scriptsize m=\lfloor\sqrt N\rfloor$，若有整数算术平方根，m即所求；无整数算数平方根时递增寻找第一个可被整除的m，所得两因子差值最小。递减求n也可，尤其是大质数样例可减少遍历次数，但要注意求n时需要判别并保证与m的大小关系

---

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int num[100001];

int main() {
    int N, m = 1, n;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &num[i]);
    sort(num, num + N, greater<int>());

    for (; m * m < N; m++);
    while(N % m != 0) m++;
    n = N / m;

    int ans[m][n];
    memset(ans, -1, sizeof(ans));
    int row = 0, col = -1, p = 0;
    while (p < N) {
        while (col < n - 1 && ans[row][col + 1] == -1) ans[row][++col] = num[p++];
        while (row < m - 1 && ans[row + 1][col] == -1) ans[++row][col] = num[p++];
        while (col > 0 && ans[row][col - 1] == -1) ans[row][--col] = num[p++];
        while (row > 0 && ans[row - 1][col] == -1) ans[--row][col] = num[p++];
    }

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (j < n - 1) printf("%d ", ans[i][j]);
            else printf("%d\n", ans[i][j]);

    return 0;
}