题解 | #最长无重复子数组#

基本思路

• 遍历过程中维护一个无重复的子数组，然后每次遇到重复数字时就重置这个无重复子数组，同时更新目前最大的无重复子数组的长度。
• 可以用双指针构建一个子数组，然后用哈希表保证子数组中没有重复数字，即先为每个不重复的数字构建哈希表，然后遍历过程为每个不重复数字计数，如果计数超过1说明当前数字重复了，需要移动窗口统计下一个不重复子数组。
• 也可以构建一个存放不重复数字的数组，利用数组的includes方法保证该数组的数字不重复，遍历过程往这个数组中存放元素，如果遇到重复数字则将目前数组的内容清空，再以当前数字为起点统计下一个不重复的子数组。

参考

https://blog.nowcoder.net/n/587f7806e5504fa29870d1ac3d81ba9b?f=comment

/*
 * @Author: LibraStalker **********
 * @Date: 2023-04-25 21:47:26
 * @FilePath: BM92-最长无重复子数组.ts
 * @Description: 
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param arr int整型一维数组 the array
 * @return int整型
 */
export function maxLength(arr: number[]): number {
    // write code here
    const maxUniqueArr: Array<number> = [];  // 保存目前最长的无重复子数组

    let right = 0;
    let maxLength = -Infinity;

    while (right < arr.length) {
        if (!maxUniqueArr.includes(arr[right])) {
            maxUniqueArr.push(arr[right]);
            maxLength = Math.max(maxLength, maxUniqueArr.length);  // 每次往无重复子数组添加元素，都更新最大无重复子数组长度，这样避免了arr只有一个元素时无法更新最大无重复子数组长度
        }
        else {  // 说明此时的right已经存在无重复数组中，将之前的无重复子数组清空，以当前right作为无重复子数组的起点
            while (maxUniqueArr.includes(arr[right])) {
                maxUniqueArr.shift();
            }
            maxUniqueArr.push(arr[right]);
        }
        ++right;
    }

    return maxLength;
}

export function maxLength_DoublePointer(arr: number[]): number {
    // write code here
    type HashObject = {
        [key: number]: number
    }
    const hashObject: HashObject = {};
    arr.forEach((num) => hashObject[num] = 0);

    let right = 0;
    let left = 0;
    let maxLength = -Infinity;

    while (right < arr.length) {
        hashObject[arr[right]]++;

        while (hashObject[arr[right]] > 1) {
            hashObject[arr[left++]]--;  // 右移左指针并减少对应的数字计数，当arr[right]小于等于1时，说明当前窗口中arr[right]不是重复元素了，此时left和right构成的滑窗是一个新的无重复子数组
        }

        maxLength = Math.max(maxLength, right-left+1);
        ++right;
    }

    return maxLength;
}