数组之双指针题

---

其实在之前我写过不少双指针得题解，刷题专练之数组移除元素
刷题专练之翻转题练习这两篇文章的题解基本就是双指针法，加上这篇文章，数组的双指针法的思想基本就已经很完善了，而且今天的代码基本都可以当作模板

一、最长连续不重复子序列

1.题目介绍

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

输入格式
第一行包含整数 n。

第二行包含 n
个整数（均在 0∼105
范围内），表示整数序列。

输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围
1≤n≤105

2.思路

首先题目需要我们找出一个没有重复数字的最长的最长的连续区间，这个问题我们可以分成两个子>问题
（1）.找出一个具有某种性质的最长的区间
（2）.这个性质是不包含重复数字
对于第一个问题找一个区间，这不就是需要双指针吗？我们用i和j来维护这个区间，那我们还需要解决不包含重复数字这种性质
我们可以这样，我们可以对区间里的数字进行统计，出现大于1的数字我们就更新，具体的实现看代码

3.

#include<stdio.h>int  max(int a,int b)//这个函数用来比较最大值
{return a>b?a:b;
}
int main()
{   const int N=100010;int a[N],b[N];int n,i,j;int res;scanf("%d",&n);for(i=0,j=0;i<n;i++)//i和j就是我们判断的区间{scanf("%d",&a[i]);++b[a[i]];//每当i往前面走的时候，我们对于进来得1数字+1，那样我们就可以判断每个数字出现的次数while(b[a[i]]>1)//如果有一个数字出现两次，那么一定是是i带进来的数，因为i以前的数我们在之前就已经检查过了{--b[a[j++]];//没当j向前走的时候我们将离开的数减一}res=max(res,i-j+1);}printf("%d ",res);return 0;
}

二、长度最小的子数组

理解了上面的题，这题基本就是水到渠成了

1.题目介绍

来源于力扣的209. 长度最小的子数组

2.思路

做了上面的题，这题就比较清楚了我们只需要更改更新方式和比较方式，具体在代码里

3.代码

int min(int a,int b)
{return a<b?a:b;
}
int minSubArrayLen(int target, int* nums, int numsSize){int i,j;int res=INT_MAX;//如果我们需要比较最小，我们就要讲res赋成最小值int sum=0;for(i=0,j=0;i<numsSize;i++){sum+=nums[i];//每当i进来时，我们就加上这个进来的数while(sum>=target){res=min(res,i-j+1);sum-=nums[j];//每当j移动时，我们将走的数从和中间减去j++;}}if(res==INT_MAX){return 0;}return res;}

三、数组元素的目标和

1.题目介绍

2.思路

这里题目给了两个升序区间，如果题目只给一个是不是很好想，我们会用两个指针，一个指向begin(i)，一个指向end(j)，如果小了begin++，如果打了就end–，可是这里是两个，其实和只有一个是同理的

3.代码

#include<stdio.h>int main()
{const int N=100010;int a[N],b[N];int i,j;int n,m,x;scanf("%d %d %d",&n,&m,&x);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<m;i++)scanf("%d",&b[i]);i=0;j=m-1;while(1){if(a[i]+b[j]<x){i++;   }else if(a[i]+b[j]>x){j--;}else{break;}}printf("%d %d",i,j);}

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。