/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @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
}
一站式解决前端面试高频算法题