无重复字符的最长子串

暴力解法(车祸现场)

二话不说，直接开撸的结果，时间复杂度和空间复杂度统统甩到脑后😎

function lengthOfLongestSubstring(str) {
    // 存放整个截取数据的队列，每个元素都是数组，其中每个数组的元素都是不重复数据
    let sameList = [
        []
    ]
    // 缓存开始截取位置的索引
    let sameIndex = 0
    for (let i = 0; i < str.length; i++) {
        const curStr = str[i]
        let sameStr = ''
        // 队列中是否存在已经添加的数据，如果有则记录下来
        const hasSame = sameList.some((item = [], index) => {
            if (item.includes(curStr)) {
                sameStr = curStr
                return true
            }
        })
        if (!hasSame) {
            sameList[sameList.length > 0 ? sameList.length - 1 : 0].push(curStr)
        } else {
            // 截取的开始索引必须从已遍历的数据中查找。保证每次开始截取的数据索引不会跑到未遍历到的数据中
            // 要截取的开始索引必须大于上一次的，防止从已经截取过的地方再次截取，不然会产生重复数据 abba
            const currentIndex = str.slice(0, i).lastIndexOf(sameStr)
            sameIndex = sameIndex < currentIndex ? currentIndex : sameIndex
            // 开始截取，截止到当前数据的前一条数据
            // 将开始索引加一是因为开始索引的位置是相同数据所在的位置
            const arr = ([...str.slice(sameIndex + 1, i)])
            // 往整个队列中添加数据：根据截取结果中是否含有当前数据，决定是和老数据拼接后放入 还是单独放进队列
            sameList.push(arr.includes(curStr) ? [curStr] : [...arr, curStr])
        }

    }
    return Math.max(...sameList.map(item => item.length))
}

// "dvdf" 3  "pwwkew" 3 "anviaj" 5  "abba" 2  "bbtablud" 6  "jxdlnaaij" 6  "abcabcbb" 3 "bbbbb" 1   "aabaab!bb" 2 
console.log(lengthOfLongestSubstring("aabaab!bb"))

滑动解法

缓存不重复字段，并在每次循环过程中更新字符最大长度

function lengthOfLongestSubstring(s) {
    let strs = ''
    let maxLength = 0
    for (let i = 0; i < s.length; i++) {
        const curStr = s[i]
        // 如果当前字符存在于缓存字符中获取，则返回当前字符所在位置，否则返回-1
        const currentIndex = strs.indexOf(curStr)
        // 缓存的不重复字符和当前字符做拼接
        strs = (strs.slice(currentIndex + 1)) + curStr
        // 每次循环就更新不重复字符的最大长度
        maxLength = Math.max(strs.length, maxLength)
    }
    return maxLength
}