leetcode-0003 无重复字符的最长子串

题目地址 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

1.滑动窗口

时间复杂度O(n) 空间复杂度O(1)

var lengthOfLongestSubstring = function(s) {
    let result = 0
    // 定义两个移动的指针
    let left = 0;
    let right = 0;
    // 定义一个统计当前滑动窗口中各个字符出现的频率
    const slideWindow = {};

    while (right < s.length) {
        const c1 = s[right]
        // 滑动窗口中，一开始让窗口的右边界向右移动
        slideWindow[c1] = slideWindow[c1] ? slideWindow[c1] + 1 : 1
        right++
        // 判断当前c1这个字符的个数是否已经大于1
        // 如果大于1，需要向右移动滑动窗口的左边界，知道c1的频率为1
        while (slideWindow[c1] > 1) {
            const c2 = s[left]
            slideWindow[c2] = slideWindow[c2] - 1
            left++
        }
        // 获取当前的滑动窗口的长度和上一次得到的滑动窗口长度的最大值
        // 这里为什么是right-left, 而不是right-left+1
        // 因为之前的right++是发生在统计完成c1的出现次数之后，我们统计滑动窗口的大小
        // 实际上是应该用right的前一个位置，因此是right-left
        result = Math.max(result, right - left)
    }
    return result
};

更多leetcode题解和数据结构方面的知识，请关注我的github:https://github.com/GuoLizhi/