【期末复习？】有关滑动窗口算法与哈希表的笔记

前言

即将期末考试，感觉自己水平明显下滑（虽然本来就没什么水平），先看点东西提升一下。

同时预告一下：据读者反映，原博客“2024XDOJ及答案”打开会卡住。个人推测是文字量太大（毕竟已经将近十万字了，笑哭），加载困难的原因，因此这里提前说明。

原博客“2024XDOJ及答案”将停止更新

同时，我会将所有题目按类别集合发布，以便查看和复习。

事先说明：本文根据网上资料搜集并自行总结而成，如有侵权，告知立删。

题目：无重复字符的最长子串
问题描述
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
输入格式
待处理的字符串s
输出格式
最长子串 的长度

这是XDOJ的P542，一道四星难题。但如果使用滑动窗口算法和哈希表算法，会比较简单。笔者将以此题为例，讲解这两种算法。

滑动窗口和哈希表是两种常见的算法技术，经常用于解决一些具有序列或子串要求的问题。它们通常结合使用，能够高效地解决问题，特别是在字符串、数组等数据结构上。

一、滑动窗口

何为滑动窗口？

移动窗口是一种通过滑动区间或子串的边界来动态调整计算范围的算法技巧。它通常用于处理涉及连续子序列的问题，尤其是当我们需要优化时间复杂度时，尤其是在处理线性时间复杂度（O(n)）的问题时。

用人话来说，就是通过调整左边界、右边界，对整个数组进行分段处理。

因此，这种算法非常适合用在对子数组的处理上。

基本操作：

1.设定窗口：定义左右指针——初始化left = right = 0，将[left, right]视为窗口。
2.开始滑动：
a.扩展窗口： 不断right++，使窗口向右扩展，直到不再符合某种条件。（找到问题的一个可行解）
b.收缩窗口：移动左边界来缩小窗口，直到重新符合条件。（寻找其他的解以获得最优解）
c.不断循环a,b,直到right触碰到边界。
按照题干要求，在right或left移动时，结果要跟着实时更新。

接下来是实践时间：
我们可以按照模板写出以下伪代码：

#include <stdio.h>
int main(){
	char s[50001] = {'\0'};
	scanf("%s", s);
	int left = 0;//定义左指针 
	int maxlen = 0, len = 0;
	for (int right = 0; s[right] != '\0';right++){
		if（出现重复字符 ）{
			left移动到某位置 //使窗口内无重复字符。
		}
		len = right - left + 1;//结果len随着right实时更新
		if (len > maxlen) maxlen = len; 
	}
	printf("%d", maxlen);
	return 0;
}

那么，如何判断字符是否重复呢？
下面，我们介绍哈希表。

二、哈希表

何为哈希表？

哈希表是一种数据结构，它通过哈希函数将键映射到哈希表的一个索引位置。哈希表支持常数时间复杂度的查找、插入和删除操作。具体来说，哈希表的主要操作是通过一个哈希函数将一个键值映射到一个数组索引，然后在该索引位置存储该值。

换言之，便是用一个值来代表我们需要的内容。

哈希表特别适合用于查找某个元素是否存在，或者统计某些元素的频率等问题。
在字符串问题中，哈希表常用来快速查找和更新元素的位置、频率或是否出现过。

在本题中，滑动窗口所要满足的条件即当前窗口中无重复字符。
而哈希表可以帮助我们：
如果当前字符已经存在于哈希表中，则说明该字符在当前窗口内已经出现过，需要收缩窗口。
如果当前字符没有出现过，则将其加入哈希表，并继续扩展窗口。

二者是如此的和谐，以至于二者近乎同时使用。

让我们完成前面的伪代码吧：

#include <stdio.h>
int main(){
	char s[50001] = {'\0'};
	scanf("%s", s); 
	int finalset[256];//ASCII码共256位，每个元素代表一个字符 
	//这里我们利用该哈希表，记录每个字符出现的最后位置
	for (int i = 0;i < 256;i++){
		finalset[i] = -1;//尚未读取到字符 
	}
	int left = 0;//定义左指针 
	int maxlen = 0, len = 0;
	for (int right = 0; s[right] != '\0';right++){
		char current_word = s[right];
		if (finalset[current_word] >= left){
			left = finalset[current_word] + 1;//移动left 
		}
		finalset[current_word] = right;//更新该字符的最后一个位置 
		len = right - left + 1;//结果len随着right实时更新
		if (len > maxlen) maxlen = len; 
	}
	printf("%d", maxlen);
	return 0;
}

这样，我们就用一种精炼简洁的方式，完成了这道所谓的四星题。