[数据结构与算法]最长无重复子数组

最长无重复子数组

题目大意

给定一个长度为 $n$ 的数组 $arr$ ，返回 $arr$ 的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

数据范围

$0\le arr.length\le 10^5$

$0<arr[i]\le 10^5$

样例

输入： [2,3,4,5]
返回值：4
说明：[2,3,4,5]是最长子数组     

解法+证明

题目需要求最长不重复的子数组，首先明确一点，子数组必须是连续的
首先明确一点：本题最大规模数据可以达到 $2e5$ 级别，如果采用双重循环，那么一定会超时（本次期末考试能过是因为数据太弱了）
先简单介绍一下：一台正常的比赛机器，$1s$ 可以跑 $1e7?1e8$ 的数据，那么如果是双重循环，在本题可以达到$4e10$ 的计算量，所以一定会超时
那么我们需要一个更加快捷的算法，来解决这道题目
//老师给的一种思路是动态规划，但鉴于我不是采取这种思路解决的，所以这种思路暂且不表（才不是想偷懒~╭(╯^╰)╮）

那么怎么做呢？

一个很简单的想法：如果所有的数字，都只出现了一次，那么答案就是长度

除了这种情况以外，我们还需要挖掘题目的性质：注意一点：一个最长不重复的子数组，对于这个子数组而言，他每个元素都是在位置上连续并且只出现一次的，换句话说，这个数组是不能变得更大的一个数组

简单证明：如果这个数组可以在左边加入一个元素，那么显然加入了新元素的新数组比原来的数组的长度要大1，与原假设矛盾，在右边加入一个元素也是类似的。

因此，可以得到一个重要结论：对于答案的这个子数组而言，其左边的第一个元素，或着往右边的第一个元素，一定在子数组中出现过且仅出现过一次

那么我们想到了什么？没错，就是计数

给出一个 $cnt$ 数组，这个数组用于记录数组元素 $a[i]$ 在一个定区间 $[left,right]$ 中出现的个数

接下来，我们只需要维护 $[left,right]$ 这个区间，保证区间中的所有数字出现且仅出现一次即可，具体到方法而言，就是我们采用双指针，在确定左端点 $left$ 后，每一次移动右端点，同时计数，如果新加入的这个数导致了当前的区间 $[left,right]$ 中某个数出现的次数大于1，那么我们就不断移动左端点，使得整个区间内所有数出现且仅出现一次即可。

最后，需要指出的是，虽然形式上我们采用了双重循环，但是本质上这段代码需要的运行上限是 $2n$ 所以不会超时

标程

双指针+计数

/**
 * 
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#define N 200005
static int cnt[N];
int maxLength(int* arr, int arrLen ) {
    //特判
    if (arrLen < 2) return arrLen;
    int maxLen = 0;
    //双指针，移动右边界
    int left = 0,right = 0;
    while(right < arrLen)
    {
        //先计数
        cnt[arr[right]]++;
        //新的计数导致了区间内某一个数字出现次数大于1
        while(cnt[arr[right]] > 1)
        {
            //从左边开始，删除数字直到区间内所有数字出现且仅出现一次
            cnt[arr[left]]--;
            left++;
        }
        //处理完成后，右区间+1，准备进入下一次循环
        right++;
        //更新答案
        maxLen = maxLen > (right - left) ? maxLen : (right - left);
    }
    return maxLen;
}