无重复字符的最长子串

发表于 | 阅读次数: |

无重复字符的最长子串

题目：给定一个字符串，找出不含有重复字符的最长子串的长度。

示例

1
2
3
输入： ""abcabcbb""
输出： 3
原因： 无重复字符的最长子串是 "abc"，其长度为 3

一、暴力解法
逐个检查所有子字符串，判断是否含有重复的字符；
就通过逐个检查就能想到这个方法肯定有很多层循环，还是一个一个的判断很消耗时间，虽然最终也能拿到正确的值，但是其时间复杂度很大。
时间复杂度: O(n3️⃣)

二、滑动窗口解法
滑动窗口，我也第一次见，并不知道其中最主要的含义，但是通过字面意思猜出一个大概，应该是把一个空间类似为窗口的移动，一段一段的进行操作；其具体的说法是：滑动窗口是数组/字符串问题中常用的抽象概念；窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）；而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j) 向右滑动1个元素，则它将变为 [i+1, j+1)（左闭，右开）。

回到问题：通过找到定义字符到索引的映射，当我们找到重复的字符时，我们可以立即跳过该窗口。
也就是说，如果 s[j] 在 [i, j) 范围内有与 j'有重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 [i，j'] 范围内的所有元素，并将 i 变为 j' + 1。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function childStrMaxLenNumEvent(strData) {
  let strLen = strData.length,
      childStrMaxLen = 0,
      storeChildStrObj = {};

  for (let i = 0, j = 0; j < strLen; j++) {
    const curStr = strData.charAt(j);
    if (storeChildStrObj.hasOwnProperty(curStr)) {
      i = Math.max(storeChildStrObj[curStr], i);
    }

    childStrMaxLen = Math.max(childStrMaxLen, j - i + 1);
    storeChildStrObj[curStr] = j + 1;
  }

  return childStrMaxLen;
}

时间复杂度： O(n)，只有索引 j 迭代了一遍，比暴力法好多了