找到字符串的最长无重复字符子串

找到字符串的最长无重复字符子串

题目描述

给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有字母都不相同)。

输入描述：

输入包含两行，第一行包含一个整数$n(1\le n\le 10^5)$，代表数组arr的长度,第二行包含n个整数，代表数组$arr(1\le arr[i]\le 10^6)$。

输出描述：

输出一个整数，代表arr的最长无重复字符的长度。

示例1

输入

4 2 3 4 5

输出

4

实例2

输入

5 2 2 3 4 3

输出

3

---

题解：

贪心。使用一个哈希表记录每个元素最近出现的位置，假设当前遍历到 i 位置，pre 表示必须以 arr[i-1] 结尾情况下，最长无重复子串开始位置的前一位置。若 pre<hash[arr[i]] ，说明在pre后面出现过 arr[i] ，则更新 pre 为 hash[arr[i]]；否则的话，pre+1 到 i 位置均是不重复的元素，直接更新最大长度即可。

代码：

#include <cstdio> using namespace std; const int N = 1000010; int n; int a[N]; int main(void) { scanf("%d", &n); int pre = 0, ret = 0; int val; for (int i = 0; i < n; ++i) { scanf("%d", &val); if (!a[val] || a[val] < pre) { if (i - pre + 1 > ret) ret = i - pre + 1; } else pre = a[val]; a[val] = i + 1; } return 0 * printf("%d\n", ret); }