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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param arr int整型一维数组 the array
 * @return int整型
 */

/**
 * 解法一：滑动窗口（reduce累加器）
 * 此题与leetcode 003 题类似
 * 思路：
 * （1）先判断数组 arr 的长度，如果 arr.length <= 1 直接返回 arr.length
 * （2）使用数组的 reduce 累加器，滑动窗口过程处理（详细过程看以下代码）
 * （3）返回最长无重复子数组的长度 maxLen
 * 时间复杂度：O(n)，n 代表数组长度，reduce 会将数组遍历一遍
 * 空间复杂度：O(1)
 */
export function maxLength(arr: number[]): number {
    if (arr.length <= 1) return arr.length
    let maxLen = 0
    
    arr.reduce((total, value) => {
        const index = total.indexOf(value)
        
        // push 到 total 尾部
        total.push(value)
        
        if (index === -1) {
            // 如果该数字没有在 total 中出现过，获取目前为止滑动窗口的最大值
            maxLen = Math.max(total.length, maxLen)
        } else {
            // 如果该数字有在 total 中出现过，则剔除掉 total 中 0 ~ index 的字符
            total = total.slice(index + 1)
        }
        
        return total
    }, [])
    
    return maxLen
}

/**
 * 解法二：滑动窗口（双指针&哈希）
 * 思路：
 * （1）先判断数组 arr 的长度，如果 arr.length <= 1 直接返回 arr.length
 * （2）窗口左右界都从数组首部开始，每次窗口优先右移右界，并统计进入窗口的元素的出现频率。
 * （3）一旦右界元素出现频率大于1，就需要右移左界直到窗口内不再重复，将左边的元素移除窗口的时候
 *     同时需要将它在哈希表中的频率减1，保证哈希表中的频率都是窗口内的频率。
 * （4）每轮循环维护最长子串的长度 maxLen
 * 时间复杂度：O(n)，外循环窗口右界从数组首右移到数组尾，内循环窗口左界同样如此，因此复杂度为O(n + n) = O(n)
 * 空间复杂度：O(n)，最坏情况整个数组都是不重复的，哈希表的长度就是数组长度
 */
export function maxLength(arr: number[]): number {
    if (arr.length <= 1) return arr.length
     
    let maxLen = 0
    const map = new Map()
    
    // 设置窗口左右边界
    for (let left = 0, right = 0; right < arr.length; right++) {
        if (map.has(arr[right])) {
            // 窗口右移进入哈希表统计次数
            map.set(arr[right], map.get(arr[right]) + 1)
        } else {
            map.set(arr[right], 1)
        }
        
        // 出现次数大于1，则窗口内有重复
        while (map.get(arr[right]) > 1) {
            // 窗口左移，同时减去该数字出现的次数
            map.set(arr[left], map.get(arr[left++]) - 1)
        }
         
        maxLen = Math.max(maxLen, right - left + 1)
    }
    
    return maxLen
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview