[数据结构与算法]LeetCode - 双指针专题

前言

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

一、双指针

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更新完之后都更新一遍j
	while (j < i && check(i, j)) j ++; // j的第一个判断条件是 j 的范围，在一个合法的范围内(这里j < i)，通过check函数检测是否满足某种性质
	// 2.处理这段区间：下面部分为每道题目具体的逻辑
}

5. 例题

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

#include <iostream>
#include <cstring>

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;
}

二、刷题

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 <iostream>
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 <iostream>

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 <iostream>

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；

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖