算法之滑动窗口

[jyzwf]

今天刷 leetcode，题目描述为求取 无重复字符的最长子串长度，在里面使用到了滑动窗口求解；
题目描述：

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

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

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

当然，可以运用暴力解决，设置 i 和 j，然后固定i，去移动j，j 移到最后的时候，再去移动 i，但上面会存在很多无用功，我们已经对某一子串进行过了一次验证，当i或j改变时，又要重新进行验证，这是没必要的，如果从索引 i 到 j - 1之间的子字符串 s {ij} 已经被检查为没有重复字符。我们只需要检查 s[j] 对应的字符是否已经存在于子字符串 s{ij}中。所以我们可以设置一个可以左右滑动的窗口，来存放当前没有重复的子串，后续就是来向右移动这个窗口来获取最大长度：

/**
 * @param {string} s
 * @return {number}
 * "aecbabcbb"
 */
var lengthOfLongestSubstring = function(s) {
    let n = s.length
    let set = new Set()
    
    let ans = 0,i=0,j=0;
    
    while(i<n && j<n){
        if(!set.has(s[j])){
            set.add(s[j++])
            ans = Math.max(ans,j-i)
        }else{
            set.delete(s[i++])
        }
    }
    
    return ans
};

不过从上面我们可以看到，当b 已存在于滑动窗口的时候，j此时不需要动，动的是i，i向右缩小窗口直到b不存在与窗口之中，也就是说，如果 s[j] 在 [i, j) 范围内有与 j' 重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 [i，j']范围内的所有元素，并将 i 变为 j' + 1，上面即为s[4] (a)，所以最后代码优化为：

/**
 * @param {string} s
 * @return {number}
 * "aedfbcbbcbb"
 */
var lengthOfLongestSubstring = function(s) {
    let n = s.length,ans = 0
    
    let map = new Map()
    
    for(let j=0,i=0;j<n;j++){
        if(map.has(s[j])){
            i = Math.max(map.get(s[j]),i)    // 处理 abba 的情况
        }
        
        ans = Math.max(ans,j-i+1)
        
        map.set(s[j],j+1)
    }
    
    return ans
};