最近我学习了双指针 ， 但是感觉思维上面还是有一点难 ， 写一篇关于双指针法的总结

双指针法:

1. 碰撞指针
2. 快慢指针
3. 不同数组中的指针

T1 乘最多水的容器

solution

定义两个指针 $i$ $j$ , $i$指向左端点 ， $j$ 指向右端点，可以发现有 $ans = min(h[i], h[j]) * (j-i)$ 显然，无论是动 $i$ 还是 $j$ ，变化后的 $(j-i)$ 的值都是一致的。所以就要让 $min(h[i], h[j])$ 的值有可能变大 , 比较 $h[i], h[j]$ 谁更小移动谁即可。

code

#include<iostream>
using namespace std;

const int N = 1e5 + 5;

int n , h[N] , ans;

int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> h[i];
	}
	int i = 1 , j = n;
	while(i < j){
		int hs = min(h[i] , h[j]);
		ans = max(hs * (j - i) , ans);
		
		if(h[i] > h[j]) j --;
		else i ++;
	}
	cout << ans;
	return 0;
}

T2 数组求和

solution

读题可以发现数组具有单调性，定义两个指针 $i$ $j$ , $i$指向A数组左端点 ， $j$ 指向B数组右端点

$if$ $a[i]+b[j]>k$ 把 $j$ 左移，使得总和减少

$if$ $a[i]+b[j]<k$ 把 $i$ 右移，使得总和增加

code

#include<iostream>
using namespace std;

const int N = 1e5 + 5;

int n , m , k;
int a[N] , b[N];

int main(){
	cin >> n >> m >> k;
	for(int i = 0 ; i < n ; i ++){
		cin >> a[i];
	}
	for(int i = 0 ; i < m ; i ++){
		cin >> b[i];
	}
	int i = 0 , j = m - 1;
	while(i < n && j >= 0){
		if(a[i] + b[j] > k) j --;
		else if(a[i] + b[j] < k) i ++;
		 
		if(a[i] + b[j] == k){
			cout << i << " " << j;
			break;
		}
	}
	return 0;
}

T3 最长连续不重复子序列

solution

用两个快慢指针 $i$ $j$，用桶数组标记重复的，若进来一个重复的数，让 $j$ 继续往右走，直到将与 $a[i+1]$ 重复的元素去掉，否者让 $i$ 指针向前遍历

记得更新 $ans = (i - j + 1)$

时间复杂度 $O(n)$

code

#include<iostream>
using namespace std;

const int N = 1e5 + 5;

int n , a[N] , to[N] , ans;

int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	int i = 1 , j = 1;
	while(i < n){
		to[a[i]] ++;
		while(j < i && to[a[i]] > 1){
			to[a[j]] --;
			j ++;
		}
		i ++;
	    ans = max(ans , i - j);
	}
	cout << ans;
	return 0;
}

每日一言

although many questions ahead of us , remember : 即使走出半生，归来任是少年

今天是我发 $blok$ 的第一天，加油！