算法：无重复字符的最长子串

Author： Lindo
发布时间：April 4, 2020
892views
2 comments
3228 words
Categories：算法

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

## 题目详解 ##

```
示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
```

## 可行-穷举 ##

那么一开始肯定是最Lowwwwwww的了

```
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let result = []
    let maxLength = 0
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            result.push(s.slice(i, j))
        }
    }
    result.forEach(array => {
        let temp
        for (let i = 0; i < array.length; i++) {
            temp = array.slice(0, i).concat(array.slice(i + 1))
            if (temp.indexOf(array[i]) > -1) {
                return
            }
        }
        if (array.length > maxLength) {
            maxLength = array.length
        }
    })
    return maxLength
};
```

## 勉强能用-键值对 ##

1. 先外层遍历一次
 2. 从外层遍历的起点开始往后新增字符，校验并记录满足条件的最大长度

```
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let map
    let maxLength = 0
    for (let i = 0; i < s.length; i++) {
        map = Object.create(null)
        let length = 1
        map[s[i]] = s[i]
        for (let j = i + 1; j < s.length; j++) {
            if (map[s[j]] !== undefined) {
                break
            } else {
                map[s[j]] = s[j]
                length++
            }
        }
        if (length > maxLength) {maxLength = length}
    }
    return maxLength
};
```

## 勉强能见人优化-滑块 ##

1. 从左至右滑动滑块，若新进字符（右）不重复，则不移除末尾字符（左）
 2. 若新进字符与已存在字符重复，则移除左起点至被重复字符的字符字串,   
   - 比如当前滑块为“abcde”，新进字符为c,则移除“abc”
 3. 滑块右移，并比较当前长度与最大长度

```
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let _window = []
    let maxLength = 0
    let index = 0
    let temp
    let tempIndex
    while (index < s.length) {
        temp = s[index]
        tempIndex = _window.indexOf(temp)
        if (tempIndex === -1) {
            _window.push(temp)
            if(_window.length > maxLength) { maxLength = _window.length}
        } else {
            _window.splice(0, tempIndex + 1)
            _window.push(temp)
        }
        index++
    }
    return maxLength
};
```

## 再优化 ##
```
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    if(!s) return 0;
    if(s.length == 1) return 1;
    
    let index, temp, len
    let arr = new Array(256) //在JavaScript中一个函数最多拥有255个参数
    arr.fill(-1)
    let startIndex = 0
    let maxLength = 0

for (let i = 0; i < s.length; i++) {
        temp = s[i].charCodeAt()
        index = arr[temp]
        if (index !== -1 && index >= startIndex) {
            len = i - startIndex
            if (len > maxLength) { maxLength = len }
            startIndex = index + 1
        }
        arr[temp] = i
    }
    if (maxLength < (s.length - startIndex)) {maxLength = s.length - startIndex}
    return maxLength
};
```

[函数表达式][1]

[1]: https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Operators/function

Last modification：April 8th, 2020 at 09:54 am

If you think my article is useful to you, please feel free to appreciate