双指针法及例题

文章目录

• 一、什么是双指针法
• 二、双指针的优点
• 三、双指针常见的类型及例题
• • 1.左右指针
  • • 和为给定数
  • 2.滑动窗口
  • • （1）连续自然数和
    • （2）强迫症
• 四、总结

一、什么是双指针法

双指针法其实就是设立两个变量来模拟双重循环遍历数组的过程，它可以解决特定的双重循环问题。 这里的指针并不是真正的指针，而是用两个int型变量来记录我们遍历到的位置，由于它的作用类似于指针，所以我们把它叫做双指针法。

二、双指针的优点

双指针法常用于对数组的操作中，一般使用双指针法可以解决的问题，使用双重循环也可以解决，双指针法相当于它的一种优化方法，让数组只遍历一遍就可以求出答案，相当于将O(n^2)算法优化为了O(n)的算法，这个是非常厉害和实用的。

三、双指针常见的类型及例题

1.左右指针

左右指针其实就是让两个指针分别从数组的左右两端向中间移动，我们通过题目来理解它。

和为给定数

测试链接

这道题，他要求两个不同位置上和为给定数的这两个数的值，我们使用双重循环很容易可以求解，但肯定会超时，所以考虑双指针法能不能用。

• 题目中只要求我们找到这两个数就行，且优先输出更小的数对，说明这两个数的寻找和它在数组中原本的位置是无关的，说明我们可以直接对该数组进行排序，因为给定数=一个较小数+一个较大数，且题目要求也是优先输出最小的，这样我们就不需要去判断它的大小了，找到的第一对就是最小的数对。
• 此时，我们就可以直接用左右指针了，i指向最小数，j指向最大数，我们判断a[i]+a[j]的大小，如果>给定数，说明总和太大了，我们想要减小总和
  可以让j–,总和就减小了，反之,如果<给定数，说明此时总和太小了，我们想要增大总和，让i++,此时总和就增大了，我们循环去进行这个过程，直到找到第一个总和为给定数的时候，即可输出。

以下为代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,sum;
const int N = 1e5+10;
int a[N];
int main() {
	cin>>n;
	for (int i = 1; i <= n; i++) cin>>a[i];
	sort(a+1,a+1+n);
	cin>>m;
	int l = 1, r = n;
	while (l < r) {
		if (a[l] + a[r] == m) {
			cout<<a[l]<<" "<<a[r];
			break; 
		}
		else if (a[l] + a[r] > m) r--;
		else l++;
	}
	if (l == r) cout<<"No";
	return 0;
}

关于左右指针我们就介绍到这里，因为左右指针其实常用到的不多，题目也比较简单，而另一种类型非常常见。

2.滑动窗口

滑动窗口其实也叫快慢指针，由于它的两个指针是时刻在变化的，像一个滑动的窗口，所以我们也叫它滑动窗口，它通常用于求一段满足特殊条件的数组段，而且这个数组段的长度是不固定的，也就是我们求解前并不知道满足题目要求的数组段到底是多长，我们可以通过题目去理解理解。

（1）连续自然数和

测试链接

这道题要求我们求一个连续的自然数段，使这一段的总和为M。

• 我们看到在数组中求一段满足条件的数组段时，其实可以直接去优先考虑滑动窗口，像这道题，我们可以设置两个指针i和j，让i一直向后遍历数组，j不动，直到从i到j的这段区间里面数的和=M的时候，我们就可以停止了，说明我们找到了第一个区间段，而如果没有=M而是直接>M了，说明这一段不满足条件，直接让j++，判断此时是否满足<M,重复去判断，直到i遍历完整个数组，就可以结束了。
• 有的小伙伴会问，为什么>M的时候直接让j++后再去判断它的总和，不用让i在回来重新从j后面开始遍历呢？这就提现到我们之后使用滑动窗口的特性了，一般使用滑动窗口时，这个数组先得有序，例如，我们这个问题中，连续自然数，必然是有序的，当我们i到j不满足的时候，我们让j++，此时总和必然是减小的，我们没有必要再让i回来了，直接让它继续接着遍历后面的数去判断，没有了这个回溯的过程，我们的时间复杂度大大被优化，减少了做重复的判断，这也是双指针的美妙所在。

（2）强迫症

这道题，它要求在给定数组中，找到一段子数组，让该子数组中最大值和最小值的差值不超过K。

• 我们要找的这段数组和它输入的顺序是无关的，我们只需要在数组中找到几个数，满足最大差值不超过K即可，所以我们考虑先对输入的数组进行排序，这样我们就不需要去找最大和最小数了，最左边就是最小数，最右边就是最大数，也符合滑动窗口的特性。
• 这个题和上一道本质上是一样的，只是让你判断的条件改变了，这道题要求的最大差值不超过K，即让 a[r]- a[l] 的值与K判断即可，大于K,说明差值大了，要缩小差值，所以l往右走，反之，r往右走，这里不在赘述。

以下为代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int n,k,t;
int main() {
	cin>>t;
	while (t--) {
		int ans = 0;
		cin>>n>>k;
		for (int i = 0; i < n; i++) cin>>a[i];
		sort(a,a+n);
		int l = 0, r = 0;
		while (l < n && r < n) {
			if (r+1 < n && a[r+1] - a[l] <= k) r++;
			else {
				ans = max(ans,r-l+1);
				l++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

四、总结

双指针的题目特征很明显，大家多做几道就会发现，它的数组一般是有序的，而且很多题不同之处也就是判断的条件不同，大家要灵活判断条件。

大家有什么问题可以直接在评论区讨论，如有错误，欢迎指正！