前端力扣刷题 | 3：hot100之 滑动窗口

3. 无重复字符的最长子串

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

示例：

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

法一：

1. 滑动窗口维护无重复子串：
   • 使用两个指针 start（窗口左边界）和 i（右边界）动态维护窗口范围。
   • 遍历字符串，逐步扩大窗口。
2. 处理重复字符：
   • 如果当前字符在窗口内重复（通过 Map 判断），调整窗口左边界 start 到重复字符的下一个位置。
3. 动态更新窗口和结果：
   • 使用 count 记录当前窗口长度。
   • 每次遍历时更新 res，保存最长无重复子串的长度。
4. 返回结果：
   • 遍历结束后，res 即为最长无重复子串的长度。

var lengthOfLongestSubstring = function(s) {
    let res = 0;
    let map = new Map();
    let count = 0;    // 当前窗口长度
    let start = 0;   // 窗口起始位置
    for(let i=0;i<s.length;i++){
        if(map.has(s[i])&&map.get(s[i])>=start){
            // 如果当前字符重复且在当前窗口内，则调整窗口长度
            start = map.get(s[i])+1;
            count = i-start
        }
        count++;
        map.set(s[i],i);   // 更新字符串最新位置
        res = Math.max(res,count);
    }
    return res;
};

• 时间复杂度：O(n)，每个字符最多被访问两次。
• 空间复杂度：O(n)，用于存储字符及其位置的 Map。

法二：

1. 滑动窗口：
   • left 和 right 是滑动窗口的左右指针。
   • right 遍历字符串，扩展窗口，检查当前字符是否已经在窗口中。
   • 如果字符重复，移动左指针 left 到重复字符的下一位置。
2. 字符位置记录：
   • 使用 Map 记录字符的最新出现位置。
   • 每当重复字符出现且位置在窗口内时，更新窗口左边界。
3. 更新结果：
   • 每次更新窗口时，计算当前窗口长度 right - left + 1，并与 res 进行比较以保持最大值。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let res = 0; // 记录最大长度
    let map = new Map(); // 用于存储字符及其最新位置
    let left = 0; // 滑动窗口的左边界

    for (let right = 0; right < s.length; right++) {
        if (map.has(s[right]) && map.get(s[right]) >= left) {
            // 如果当前字符已经存在于窗口中，更新左边界
            left = map.get(s[right]) + 1;
        }
        // 更新字符最新位置
        map.set(s[right], right);
        // 计算窗口长度
        res = Math.max(res, right - left + 1);
    }

    return res;
};

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例：

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释：
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

var findAnagrams = function(s, p) {
    let res = [];
    let pCount = Array(26).fill(0); // 记录 p 中各字符的出现次数
    let sCount = Array(26).fill(0); // 记录滑动窗口中各字符的出现次数
    const aCode = 'a'.charCodeAt(0); // 字符 'a' 的 ASCII 值，用于映射字符到数组索引

    // 初始化 p 的字符计数
    for (let char of p) {
        pCount[char.charCodeAt(0) - aCode]++;
    }

    for (let i = 0; i < s.length; i++) {
        // 当前字符加入窗口
        sCount[s[i].charCodeAt(0) - aCode]++;

        // 如果窗口长度大于 p 的长度，移除最左边的字符
        if (i >= p.length) {
            sCount[s[i - p.length].charCodeAt(0) - aCode]--;
        }

        // 判断窗口内字符计数是否与 p 的字符计数相等
        if (sCount.toString() === pCount.toString()) {
            res.push(i - p.length + 1); // 记录起始索引
        }
    }

    return res;
};