【编程笔记】双指针算法·最长连续不重复子序列

双指针算法，顾名思义，需要两个指针，且可以做到将时间复杂度为O(n^2)的算法变为O(n)的算法。

常见问题分类：

（1）对于一个序列，用两个指针对一段区间进行维护

（2）对于两个序列，使之维护某种次序，例如归并排序中合并两个有序序列的操作

最长连续不重复子序列

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 n。

第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

最长连续不重复子序列思路

很明显，这里符合“对于一个序列，用两个指针维护一段区间”的情况，故采用双指针算法

1.遍历数组a中的每个元素a[i],对于每个i，查找j，使得双指针[j，i]保持以a[i]结尾的最长连续不重复子序列，长度为i-j+1，并将该长度和r中的较大者更新为r.

2.由于[j，i-1]是上一步得到的最优解（正在比较中的最长连续不重复子序列），如果[j，i]中有重复元素，则一定是a[i]，所以将j向右移动，直到a[i]不重复为止。

3.用数组s记录子序列a[j  ~ i]中每个元素的出现次数(s[a[i]]++)

4.在遍历中，若a[i]重复则右移j，将a[j]减一（a[i]出现次数）。同时先减后移动j指针来避免不必要的比较。

出现重复的情况：

将j指针后移，且先减次数在后移指针。1，5，2因为已经不在正在比较中的子序列中，它们的出现次数依次减去一。

最后将已有的最优解和i-j+1比较，取长的那条为新的最优解。

无语，一开始竟然没有明白。

夕弦的图片由NovalAI生成。