/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 * 
 * @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