文章目录

• 前言
• 一、双指针
• • • 1. 类型
    • 2. 作用
    • 3. 用法
    • 4. 代码模板
    • 5. 例题
• 二、刷题

前言

        今天算法的内容是：双指针。
 

一、双指针

1. 类型

    ① 两个指针指向两个不同的序列，一个指针指向一个序列，另一个指针指向另一个序列，两个指针维护的是某种次序，例如归并排序中归并的过程。
    ② 两个指针指向指向同一个序列，这两个指针维护的是一段区间，例如快速排序中划分区间的过程。

2. 作用

核心思想：本来用两重循环枚举两个指针，通过运用某种单调的性质，本来是用 O(n²) 来枚举所有的情况，用双指针算法只需要枚举 O(n) 个状态，将时间复杂度优化为 O(n)。

3. 用法

    ① 前提：有序；
    ② 凡是枚举两个端点的题目，先从暴力的做法想起。优化的话基本都要考虑单调性；
    ③ 如何优化？本质上是找两个指针 i和 j有什么样的规律， i和 j有没有单调性，有单调性的话就可以考虑用双指针；
    ④ 证明单调性；

4. 代码模板

// for (i = 0, j = 0; i < n; i ++) // i从0开始，j从某一个数开始(这里从0开始)，i整个扫描一遍区间{// 1：找到区间。每次i更新完之后都更新一遍jwhile (j < i && check(i, j)) j ++; // j的第一个判断条件是 j 的范围，在一个合法的范围内(这里j < i)，通过check函数检测是否满足某种性质// 2.处理这段区间：下面部分为每道题目具体的逻辑}

5. 例题

输出带有空格的字符串，输入的字符串为 abc def ghi

#include #include using namespace std;int main() {char str[100010];fgets(str, 1000, stdin);int n = strleng(str);for (int i = 0; i < n; i ++) {int j = i;while (j < n && str[j] != ' ') j ++;for (int k = i; k < j; k ++) cout << str[k];cout << endl;i = j;}return 0;}

LeetCode 485. 最大连续 1 的个数 原题链接

class Solution {public:    int findMaxConsecutiveOnes(vector<int>& nums) { int res = 0; for (int i = 0; i < nums.size(); i ++) {     if (nums[i] == 0) continue;     int j = i + 1;     while (j < nums.size() && nums[j] == 1) j ++;     res = max(res, j - i);     i = j; } return res;    }};

二、刷题

Acwing 799. 最长连续不重复子序列 原题链接

    1. 暴力解法

for (int i = 0; i < n; i ++) { // 先枚举终点    for (int j = 0; j <= i; j ++) { // 再枚举起点，起点和终点可以是同一个数if (check(j, i)) // 检查一下j到i的这段区间是否满足某种要求{    // 如果成立，更新下res    res = max(res, i - j + 1);    }    }}

    2. 双指针解法

for (int i = 0, j = 0; i < n; i ++) {  // (1)    // 1.找到合法区间    while (j < i && check(j, i)) j ++; // (2)// 2.处理区间：找到区间后更新答案即可res = max(res, i - j + 1);   // (3)}

• 基本思想：每次都枚举 i，看以 i为区间的右端点，区间的左端点 j最远能在什么位置，使得 j到 i这个区间之间没有重复的数字。
• $(1)$ i 的含义：区间的右端点；
     j 的含义：区间的左端点 j离 i最远能到的位置，每次枚举 i都要求一个 j；
• $(2)$ check( ) 的含义：j到 i这个区间里包含重复元素时，j需要向右移动，直到移动到 j和 i之间没有重复元素为止。当结束 while循环，j停下时，对应的就是 j的新位置，此时 i和 j之间不包含重复元素；
     check() 的实现：开一个 s 数组，动态记录下当前这个区间里每个数出现多少次，每次 i往后移动一位相当于在区间中加入一个新的数，此时 s[a[i]] ++，每次 j往后移动一位相当于在区间中删除一个数 s[a[j]] --，这样就可以动态的统计出来这个区间中有多少个数；
     前一个 i结束时对应的 j这段区间中是没有重复元素的，每次新加入一个数，如果当前区间中有重复数了此时 s[a[i]] > 1，那么重复的数一定是新加入的这个数 a[i]（因为要保证连续的一段区间没有重复的数），j往后走的话要将 a[i]这个值去掉一个才可以，这样 i和 j之间就没有重复元素了，然后更新下答案。
• $(3)$ 对于所有的 i，求 i和 j区间长度的最大值。
• 证明 j具有单调性。

#include using namespace std;const int N = 100010;int a[N], s[N];int n;int main(){    scanf("%d", &n);    for (int i = 0; i < n; i ++) scanf("%d", &a[i]); int res = 0;    for (int i = 0, j = 0; i < n; i ++)    { s[a[i]] ++; while (j <= i && s[a[i]] > 1)  {     s[a[j]] --;     j ++; } res = max(res, i - j + 1);    }    printf("%d\n", res); return 0;}

Acwing 800. 数组元素的目标和 原题链接

    1. 暴力解法

for (int i = 0; i < n; i ++) { // 枚举第一个数组    for (int j = 0; j < n; j ++) // 枚举第二个数组if (a[i] + b[j] == x) { 输出答案     break;}}

    2. 双指针解法

for (int i = 0, j = m - 1; i < n; i ++) {// (1)    while (j >=0 && a[i] + b[j] > x) j --; // (2)    // 具体题目的逻辑    if (a[i] + b[j] == x)    // (3)    输出答案}

• A 数组和 B 数组都是单调递增的；
• $(1)$ 如果小于目标值 x，i指针后移；
• $(2)$ 如果大于目标值 x，j指针前移；
• $(3)$ 如果等于目标值 x，输出答案；

#include using namespace std;const int N = 1e5 + 10;int n, m, x;int a[N], b[N];int main(){    scanf("%d%d%d", &n, &m, &x);    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);    for (int i = 0, j = m - 1; i < n; i ++ )    { while (j >= 0 && a[i] + b[j] > x) j -- ; if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;    }    return 0;}

LeetCode 167. 两数之和 II - 输入有序数组

class Solution {public:    vector<int> twoSum(vector<int>& numbers, int target) { int n = numbers.size(); vector<int> res; int l = 0, r = n - 1; while (l < r) {     if (numbers[l] + numbers[r] > target) r --;     else if (numbers[l] + numbers[r] < target) l ++;     else {  res.push_back(l + 1);  res.push_back(r + 1);  break;     } } return res;    }};

• 区别于上一个题，此题是在一个数组中找目标值 target。

Acwing 2816. 判断子序列 原题链接

• 题意：从前往后看 A数组 里面每一个数是否可以顺次匹配 B数组 里面的一个子序列。
• 思路：从前往后扫描 B数组 里的每一个数，每扫描一个数时判断 B 的当前数和 A 的当前数是否相同，如果相同则将 A 的当前数匹配到 B 的当前数。即找到 B数组中第一个和 A 数组里相同的数时将将其匹配到一起。如果 B 数组遍历完之后，A 数组里面的每一个数都找到一个和 B 数组匹配的数则成功，否则失败。

#include using namespace std;const int N = 100010;int a[N], b[N];int main(){    int n, m;    scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++) scanf("%d", &a[i]);    for (int i = 0; i < m; i ++) scanf("%d", &b[i]); int i = 0, j = 0; while (i < n && j < m)    { if (a[i] == b[j]) i ++; // (1) j ++;// (2)    } if (i == n) puts("Yes");    else puts("No"); return 0;    }

    $(1)$ A 数组当前数和 B 数组当前数匹配了 i指针才后移一位；
    $(2)$ 每次 j都往后移动一位；

剑指 Offer 57 - II. 和为s的连续正数序列 原题链接

• i为区间的左端点，j为区间的右端点；如果每个 i都会对应一个 j使得 i到 j这段区间和为 target，随着 i的增大，j是否也是严格单调递增的呢？

• i往后移动到 i'，因为是正整数序列，如果 j往前移动或者是不动，从 i'到 j'的和是一定是 < target；因为要保证 i到 j这段区间和 = target，所以当 i往后移动时，j一定也是往后移动的。

 vector<vector<int>> res; for (int i = 1, j = 1, s = 1; i <= target; i ++) { // (1)     while (s < target) s += ++ j;// (2)     if (s == target && j - i + 1 > 1) {// (3)  vector<int> line;  for (int k = i; k <= j; k ++) line.push_back(k);  res.push_back(line);     }     s -= i;// (4) } return res;    }};

    $(1)$ i为区间左端点，j为区间右端点；
    $(2)$ 区间和 < target，j一直往后移；
    $(3)$ 找到区间和为 target的区间存入结果数组
    $(4)$ i往后移动一位前，需要从区间中减去当前 i；

医疗百科