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

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

题目详解

示例 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
};

勉强能用-键值对

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

/**
 * @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
};

勉强能见人优化-滑块

从左至右滑动滑块，若新进字符（右）不重复，则不移除末尾字符（左）
若新进字符与已存在字符重复，则移除左起点至被重复字符的字符字串,

比如当前滑块为“abcde”，新进字符为c,则移除“abc”

滑块右移，并比较当前长度与最大长度

/**
 * @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
};

函数表达式