leetcode 滑动窗口 ｜ 刷题打卡

题目描述

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

示例 1:

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

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

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

输入: s = ""
输出: 0
 
提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路

1. 定义一个对象 map

var lengthOfLongestSubstring = function (s) {
    let map = {}
    let l = 0
    let r = -1
    let res = 0
    while (l < s.length) {
        if (r + 1 < s.length && map[s[r + 1]] == undefined) {
            map[s[++r]] = true
        } else {
            map[s[l++]] = undefined
        }
        res = Math.max(r - l + 1, res)
    }
    return res
};

思路二

var lengthOfLongestSubstring = function (s) {
    let len = s.length
    if (!len) return 0
    let has = {}
    let max = 0
    let left = 0
    for (let right = 0; right < len; right++) {
        let moveLeft = has[s[right]]
        if (moveLeft) {
            left = Math.max(left, moveLeft)
        }
        has[s[right]] = right + 1
        max = Math.max(max, right - left + 1)
    }
    return max
};

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 示例 2:

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

思路 尽在注释中

// s: "cbaebabacd" p: "abc"
var findAnagrams = function (s, p) {
    let res = [];
    let left = 0,
        right = 0;
    let needs = {},
        windows = {};
    let match = 0;
    // 将需要匹配的收集数据 此时 needs = {a: 1, b: 1, c: 1}
    for (let i = 0; i < p.length; i++) {
        needs[p[i]] ? needs[p[i]]++ : (needs[p[i]] = 1);
    }
	
    let needsLen = Object.keys(needs).length;
    
    while (right < s.length) {
        let c1 = s[right];
		
        if (needs[c1]) {
            windows[c1] ? windows[c1]++ : (windows[c1] = 1);
            if (windows[c1] == needs[c1]) {
                match++;
            }
        }
        right++;
        
        // 将left移动起来
        while (match === needsLen) {
        	// 比较关键的一步 字符串需要是连续的
            if (right - left == p.length) {
                res.push(left);
            }
            let c2 = s[left];
            if (needs[c2]) {
                windows[c2]--;
                if (windows[c2] < needs[c2]) {
                    match--;
                }
            }
            left++;
        }
    }

    return res
};