Jessica's Reading Problem

Jessica's Reading Problem

SCUACM2022集训前训练-数据结构 - Virtual Judge (vjudge.net)

双指针

假设当前枚举的区间是 \([l,r]\), 且是以 \(r\) 为右端点的最大的可以满足条件的 \(l\), 那么 \(r++\) 时这个 \(l\) 肯定还能满足条件，所以 \(l\) 不会回退，可以用双指针

用 map 记录当前区间是否能覆盖所有知识点 (now.size() == m), 当某一个知识点的次数为 0 时，在 map 里删去

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n;
int a[N];

int main()
{
	scanf("%d\n", &n);
	map alls;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", a + i);
		alls[a[i]]++;
	}
	int m = alls.size();
	int ans = n;
	map now;
	
	for (int l = 1, r = 1; r <= n; r++)
	{
		now[a[r]]++;
		while(l <= r && now.size() == m)
		{
			ans = min(ans, r - l + 1);
			now[a[l]]--;
			if (now[a[l]] == 0)
				now.erase(a[l]);
			l++;
		}
	}
	printf("%d\n", ans);
	return 0;
}
双指针

相关

leetcode 165.比较版本号 （双指针）

数据结构，滑动窗口，双指针，LeetCode，相关题目汇总

双指针算法

LC209双指针

双指针算法基本原理和实践（一）

双指针算法之数组反转

【每日一题】【链表or双指针循环条件】2022年2月26日-NC96 判断一个链表是否为回文结

双指针 + 滑动窗口 寒假每日一题 品种邻近

代码随想录：双指针法

977.双指针之有序数组的平方和

力扣16题：最接近的三数之和（排序、双指针解决）

[双指针] [读写指针][ 字符串/数据 压缩] 443. 压缩字符串

标签