yao同学

滑动窗口

崧云悠揽月
June 10, 2024

目录

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

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

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

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

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
代码 ​
ts
function lengthOfLongestSubstring(s: string): number {
    if (s.length <= 1) return s.length;

    let max = 1;
    let win:string[] = [];
    let left = 0;
    let right = 1;
    win.push(s[left]);

    while(right < s.length) {
        let rc = s[right];
        right++;

        while(left < right && win.includes(rc)) {
            left++;
            win.shift();
        }
        max = Math.max(max, win.length);
    }

    return max;
};

76.最小覆盖子串 ​

困难题，放弃

567.字符串的排列 ​

题目描述 ​
ts
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false
代码 ​
ts
function checkInclusion(s1: string, s2: string): boolean {
    if (s2.length < s1.length) return false;

    const cnt = new Array(26).fill(0);
    for (let i = 0; i < s1.length; i++) {
        cnt[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)]--;
    }

    let left = 0;
    let right = 0;
    while(right < s2.length) {
        const oo = s2[right].charCodeAt(0) - 'a'.charCodeAt(0);
        cnt[oo]++;

        while(cnt[oo] > 0) {
            cnt[s2[left].charCodeAt(0) - 'a'.charCodeAt(0)]--;
            left++;
        }

        if (right - left + 1 === s1.length) return true;
        right++;
    }

    return false;
};
ts
// 执行用时14.29%，消耗内存用时5.36%
function checkInclusion(s1: string, s2: string): boolean {
    if (s2.length < s1.length) return false;

    let cnt1 = new Array(26).fill(0);
    let cnt2 = new Array(26).fill(0);
    for (let i = 0; i < s1.length; i++) {
        ++cnt1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)];
        ++cnt2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)];
    }

    if (cnt1.toString() === cnt2.toString()) return true;

    for (let i = s1.length; i < s2.length; i++) {
        cnt2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        cnt2[s2[i - s1.length].charCodeAt(0) - 'a'.charCodeAt(0)]--;
        if (cnt1.toString() === cnt2.toString()) return true;
    }

    return false;
};

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

题目描述 ​
ts
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 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" 的异位词。
代码 ​
ts
function findAnagrams(s: string, p: string): number[] {
    if (s.length < s.length) return [];

    const cnt = new Array(26).fill(0);
    for (let i = 0; i < p.length; i++) {
        cnt[p[i].charCodeAt(0) - 'a'.charCodeAt(0)]--;
    }

    let left = 0;
    let right = 0;
    let result: number[] = [];
    while (right < s.length) {
        const o_o = s[right].charCodeAt(0) - 'a'.charCodeAt(0);
        cnt[o_o]++;

        while (cnt[o_o] > 0) {
            cnt[s[left].charCodeAt(0) - 'a'.charCodeAt(0)]--;
            left++;
        }

        if (right - left + 1 === p.length) {
            result.push(left);
        }
        right++;
    }

    return result;
};

粤ICP备2022123940号-1