基础算法第四期 ：双指针算法（求最长重复子序列）

前言

双指针算法其实在真正意义上算不上是数据结构，其本质是对暴力解法进行优化。其实双指针算法并不难，只是在某些情况下题目可能提示的不明确而难以想到该算法来进行优化，多做点题掌握方法即可学会，接下来我将以题目的形式来对双指针算法进行讲解！！！

双指针算法模板：

for(int i = 0，j=0; i <ｎ; i++)

{

? ? ? ? while(j < i && check(i, j))

? ? ? ? ? ? ? ? j++;

? ? ? ? //具体题目的解题思路

}、

一、双指针算法问题1

求最长的不重复连续区间的长度

?

该问题的正常思路也是最容易想到的就是双层for循环嵌套的暴力解法，但是在做题时我们应该注意一下题目中所给的范围，一般在10的5次方及以上就不能进行双层循环嵌套，就要考虑进行优化了，上面的题就是进行了优化.

AC代码：

#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N],b[N],n,maxs;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1,j=1;i<=n;i++){
		b[a[i]]++;//i向右移
		while(j<=i && b[a[i]]>1)
		{
			b[a[j]]--;
			j++;//j也向右移动
		}
		maxs=max(maxs,i-j+1);
	}
	cout<<maxs<<endl;
	return 0;
}

思路讲解：需设两个数组，一个数组用来储存输入的值，另一个数组来统计在i-j区间内是否有重复地，如果没有重复地则i++，让i向右移动，使得该区间内的长度增加1，如果有重复地，则让j++，让j向右移动，j++之后会使得重复地数减去一个，因此要进行b[a[j]]--,如此一直循环下去即可求出最长连续子序列。

二、双指针算法问题2

数组元素的目标和

常规做法直接进行暴力即可，但是会超时因此要进行优化。

AC代码：

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

const int N = 100010;
int n, m;
int x;
int a[N], b[N];
int main()
{
    cin >> n >> m >> x;
    for (int i = 0; i < n;i ++) cin >> a[i];
    for (int j = 0; j < m;j ++) cin >> b[j];
    for (int i = 0, j = m - 1; i < n; i ++) // 双指针算法 设置两个指针i,j 
    // i从前往后走 j从后往前走
    {
        while (j >= 0 && a[i] + b[j] > x) j --; // 首先需要判断一下是否 i,j走出界
                                                // 然后判断一下首尾的元素的和是否大于目标值x
                                                // 如果大于那么j--缩小范围
        if (a[i] + b[j] == x) // 如果等于了 就输出结果
        {
            printf("%d %d\n", i, j);   
            break;
        }
    }
    return 0;
}

思路讲解：因为题目中已经给出是升序进行排列因此我们不需要再进排序，要求出目标和我们只需要将两个数组一个从前往后遍历，一个从后往前遍历即可，因为数据保证有唯一的解，因此找到之后输出完直接跳出即可，如果相加大于目标元素，说明我们从后往前遍历所给的数较大因此要j--，从而使得两数之和变下，同理如果相加小于目标元素我们只需将i--。

总结

以上就是我对双指针的简介谢谢大家观看！！！