# NC41.最长无重复子数组

# 题目描述 (opens new window)

TIP

知识点：哈希、双指针、数组

关联企业：阿里巴巴、虾皮信息、高途集团、字节跳动

# 算法思路

这道题目和leetcode上面的第3题非常类似，leetcode那道题目给定的是一个字符串，这道题目给定的是一个数组。但是算法思路是一样的；

主要用到的思想是：滑动窗口。

什么是滑动窗口？

其实滑动窗口可以看成一个队列，比如题目中的abcabcbb, 进入这个队列（窗口）为abc，此时字符串没有重复元素，满足题目要求，当再进入一个a,也就是当窗口向右扩大的时候，队列变成了abca，我们发现了重复的字符a, 这个时候就已经不满足要求，所以，我们要移动这个队列。

如何移动呢？

我们只需要把队列的左边的元素移除出去就可以了，直到满足题目要求!

一直维持这样的队列，找出队列出现最长的长度时候，求出解。

具体实现:

在js中我们使用一个数组来维护滑动窗口

遍历字符串，判断字符串是否在滑动窗口数组里面

不在则push进数组
在则删除滑动窗口数组里相同字符以及相同字符前的字符，然后将当前字符push进数组
然后将max更新为当前最长子串的长度

遍历完成，返回max即可。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @param arr int整型一维数组 the array
 * @return int整型
 */
function maxLength(arr) {
  let res = [];
  let max = 0;

  for (let i = 0; i < arr.length; i++) {
    // 判断滑动窗口中是否包含当前的这个数组元素
    let index = res.indexOf(arr[i]);
    if (index !== -1) {
      // 说明存在了
      res.splice(0, index + 1); // 将当前字符连它之前的元素全部删除掉
    }
    res.push(arr[i]);
    max = Math.max(res.length, max);
  }
  return max;
}
module.exports = {
  maxLength: maxLength,
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param arr int整型一维数组 the array
 * @return int整型
 */
export function maxLength(arr: number[]): number {
  let res: number[] = [];
  let max: number = 0;

  for (let i = 0; i < arr.length; i++) {
    // 判断滑动窗口中是否包含当前这个数组元素
    let index: number = res.indexOf(arr[i]);
    if (index !== -1) {
      // 说明已经存在
      res.splice(0, index + 1); // 将当前元素和它之前的元素全部截取
    }
    // 将最新的元素放在最后
    res.push(arr[i]);
    max = Math.max(res.length, max);
  }
  return max;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这道题目还可以使用双指针的思路来解决，我们可以使用两个指针 i和j，最开始的时候都指向第一个元素，然后往后面移动，把扫描过的元素都放到map中，如果i扫描过的元素没有重复就一直往后面移动，顺便记录一下最大值max, 如果i扫描过的元素有重复的，就改变j的值。

# 复杂度分析

时间复杂度:

外层循环遍历整个数组,时间复杂度为 O(n)。
在内层循环中,使用 indexOf 方法查找当前元素是否在窗口中,最坏情况下需要遍历整个窗口,时间复杂度为 O(m),其中 m 为窗口的大小。
splice 操作的时间复杂度为 O(m),因为需要移动数组元素。

综合起来,时间复杂度为 O(n*m),其中 n 为数组长度,m 为最长子序列的长度。在最坏情况下,m = n,时间复杂度为 O(n^2)。

空间复杂度:

使用了一个额外的数组 res 来存储窗口元素,最坏情况下,整个数组都不包含重复元素,空间复杂度为 O(n)。因此,这个解法的时间复杂度为 O(n^2),空间复杂度为 O(n)。