案例

长度最小的子数组(中)

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题思路

如果想到了滑动数组和双指针，那就可以一步一步来，比如说先创建双指针，然后思考如何让它两边可以动起来，那就可以有一个sum来计算总数是否超过target，如果超过了，那么左指针就往右移动即l++，再比较并记录答案，最后返回记录的答案即可。

function minSubArrayLen(s, nums) {
    const n = nums.length;
    if (n === 0) {
        return 0;
    }

    // 初始化双指针、当前子数组和以及最小长度
    let start = 0;
    let end = 0;
    let sum = 0;
    let ans = Infinity;

    // 移动 end 指针，扩展当前子数组
    while (end < n) {
        sum += nums[end];

        // 若当前子数组的和大于等于目标值 s，则尝试缩小子数组长度
        while (sum >= s) {
            // 更新最小长度
            ans = Math.min(ans, end - start + 1);
            // 移动 start 指针，缩小当前子数组
            sum -= nums[start];
            start++;
        }

        // 继续扩展当前子数组
        end++;
    }

    // 若最小长度仍然为初始值 Infinity，则说明不存在符合条件的子数组
    return ans === Infinity ? 0 : ans;
}

无重复字符的最长子串(中)

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

解题思路

1. 初始化变量：ans 用于存储最长子串的长度，left 作为滑动窗口的左边界，window 集合用于维护窗口内的唯一字符。
2. 通过右指针 (right) 从字符串的开头迭代到结尾。
3. 对于右边界的每个字符 c：
   • 检查 c 是否已经在窗口集合中。
   • 如果是，则将窗口的左边界 (left) 向右移动，直到窗口不再包含 c 的重复字符。在左边界移动时从集合中移除字符。
4. 将当前字符 c 添加到窗口集合中。
5. 使用当前窗口的最大长度更新 ans 变量 (right - left + 1)。
6. 重复步骤 3-5 对字符串中的所有字符执行。
7. 返回 ans 的最终值，表示给定字符串中没有重复字符的最长子串的长度。

// 计算给定字符串中无重复字符的最长子串长度的函数
var lengthOfLongestSubstring = function(s) {
    let ans = 0; // 存储最长子串长度的变量
    let left = 0; // 窗口左边界的指针
    const window = new Set(); // 用 Set 数据结构维护窗口内的字符集合

    for (let right = 0; right < s.length; right++) {
        const c = s[right]; // 当前窗口右边界的字符

        // 当窗口内已存在当前字符 c 时，移动左边界，确保窗口内无重复元素
        while (window.has(c)) {
            window.delete(s[left++]); // 删除窗口左边界的字符，并将左边界向右移动
        }

        window.add(c); // 将当前字符 c 加入窗口内
        ans = Math.max(ans, right - left + 1); // 更新最长子串长度，取当前窗口长度与已知最大长度的较大值
    }

    return ans; // 返回最长子串长度
};

串联所有单词的子串(难)

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

解题思路

整体思路就是利用滑动窗口，关键就是在于如何判断判断子串是否符合条件。

1. 初始化： 设置窗口的左右指针 left 和 right，初始都指向字符串的开头，然后遍历每个可能的起始位置（单词的长度范围）。
2. 词频表： 维护两个词频表，wordMap 用于记录 words 中每个单词的出现次数，currentWordMap 用于记录当前窗口内单词的出现次数。
3. 滑动窗口： 从每个可能的起始位置开始，移动右指针 right，依次获取当前窗口内的单词。如果当前单词不在 wordMap 中，说明窗口内的单词无法构成串联子串，重置 currentWordMap 和左指针 left。
4. 更新词频表： 更新 currentWordMap 中当前单词的出现次数。然后，通过移动左指针 left，排除多余的单词，确保窗口内的单词都符合要求。
5. 判断是否找到串联子串： 在窗口滑动的过程中，判断是否找到了符合条件的串联子串，即窗口的长度是否等于 words 中所有单词连接起来的长度。
6. 记录结果： 如果找到了符合条件的串联子串，记录当前窗口的左指针 left，表示找到一个匹配的起始位置。
7. 遍历完成： 遍历完成后，返回所有记录的起始位置作为结果。

优化空间(self)

• 性能考虑： 使用了 slice 和 padEnd 来分割字符串，这可能涉及一些额外的复制操作。在处理大型字符串时，可能会影响性能。而在我的实现中，直接使用了 substr。
• 可读性： 一些变量名和函数名可以更具体一些，使得代码更易于理解。例如，judeInclude 可以改成 isSubarrayValid，areArraysEqual 可以改成 areArraysPermutations。
• 避免重复计算： 在 areArraysEqual 中，使用了两次 countElements，可以考虑在外部先计算一次并传入两次使用，避免重复计算。
• 逻辑调整： 在 areArraysEqual 中，可以先比较数组长度，再比较元素，这样可能会更高效。

self

// 主程序
var findSubstring = function (s, words) {
    let L = 0;
    let R = words.length * words[0].length - 1;
    let ans = []
    while (R < s.length) {
        // 判断判断子串是否符合条件
        if (judeInclude(s.slice(L, R + 1), words)) {
            ans.push(L);
        }
        L++;
        R++;
    }
    return ans;
};

function judeInclude(substr, str) {
    const arr = splitString(substr, str[0].length)
    return areArraysEqual(arr,str)
}

// 辅助函数，统计一个数组中每个元素出现的次数
function countElements(arr) {
    return arr.reduce((obj, element) => {
        obj[element] = (obj[element] || 0) + 1;
        return obj;
    }, {});
}

// 判断两个数组是否完全相等
function areArraysEqual(arr1, arr2) {
    const count1 = countElements(arr1);
    const count2 = countElements(arr2);
    for (const key in count1) {
        if (!count2.hasOwnProperty(key) || count1[key] !== count2[key]) {
            return false;
        }
    }
    return true;
}

// 分割字符串
function splitString(str, c) {
    const arr = [];
    for (let i = 0; i < str.length; i += c) {
        const sub = str.slice(i, i + c).padEnd(c, " ");
        arr.push(sub);
    }
    return arr;
}

AI

function findSubstring(s, words) {
    if (s.length === 0 || words.length === 0) {
        return [];
    }

    const wordLength = words[0].length;
    const wordCount = words.length;
    const wordMap = {};

    // 初始化词频表
    for (const word of words) {
        wordMap[word] = (wordMap[word] || 0) + 1;
    }

    const result = [];

    // 遍历字符串，尝试每个可能的起始位置
    for (let i = 0; i < wordLength; i++) {
        let left = i, right = i;
        let currentWordMap = {};

        while (right + wordLength <= s.length) {
            const currentWord = s.slice(right, right + wordLength);
            right += wordLength;

            if (!(currentWord in wordMap)) {
                // 重置词频表和左指针，当前单词不在 words 中
                currentWordMap = {};
                left = right;
            } else {
                // 更新当前词频表
                currentWordMap[currentWord] = (currentWordMap[currentWord] || 0) + 1;

                // 移动左指针，排除多余的单词
                while (currentWordMap[currentWord] > wordMap[currentWord]) {
                    const leftWord = s.slice(left, left + wordLength);
                    currentWordMap[leftWord]--;
                    left += wordLength;
                }

                // 判断是否找到了一个串联子串
                if (right - left === wordCount * wordLength) {
                    result.push(left);
                }
            }
        }
    }

    return result;
}

最小覆盖子串(难)

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

解题思路

本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

fig1

如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。

具体流程

1. 初始化变量：设置minLen为s.length + 1，start为s.length，map为一个空对象，missingType为0。其中，minLen表示最小窗口长度，start表示最小窗口的起始位置，map用于记录目标字符串t中各字符的出现次数，missingType表示当前还缺少的字符种类数。
2. 遍历目标字符串t，统计每个字符的出现次数，并更新map和missingType。
3. 使用两个指针l和r，表示窗口的左右边界，初始化为0。移动右指针r，扩展窗口，同时更新map中对应字符的出现次数。
4. 当窗口包含t中所有字符时，进入内循环（missingType == 0）。在内循环中，比较当前窗口长度与minLen的关系，如果更短则更新minLen和start的值。
5. 移动左指针l，缩小窗口，同时更新map中对应字符的出现次数。如果某个字符的出现次数大于0，表示当前窗口缺少该字符，此时更新missingType。
6. 重复步骤3到步骤5，直到右指针r到达字符串s的末尾。
7. 最终，返回最小窗口的子串，如果不存在则返回空字符串。

该算法的关键点在于通过移动左右指针维护一个滑动窗口，不断更新窗口内字符的出现次数，以找到包含目标字符串t所有字符的最短子串。

// 函数接收两个字符串 s 和 t，目的是在 s 中找到包含 t 所有字符的最小窗口子串
const minWindow = (s, t) => {
    let minLen = s.length + 1; // 最小窗口长度的初始值为 s 长度 + 1
    let start = s.length;      // 最小窗口的起始位置初始值为 s 长度
    let map = {};              // 存储目标字符和对应的缺失个数的映射
    let missingType = 0;       // 当前缺失的字符种类数

    // 遍历字符串 t，初始化目标字符计数映射
    for (const c of t) {
        if (!map[c]) {
            missingType++; // 需要找齐的种类数 +1
            map[c] = 1;
        } else {
            map[c]++;
        }
    }

    let l = 0, r = 0; // 左右指针初始化
    while (r < s.length) {
        let rightChar = s[r]; // 获取右指针指向的新字符

        // 如果新字符是目标字符，将其对应的缺失个数减一
        if (map[rightChar] !== undefined) map[rightChar]--;

        // 如果新字符的缺失个数变为 0，缺失的种类数减一
        if (map[rightChar] == 0) missingType--;

        // 当前窗口包含所有字符的前提下，尽量收缩窗口
        while (missingType == 0) {
            // 如果窗口宽度比 minLen 小，更新 minLen 和最小窗口的起点
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                start = l;
            }

            let leftChar = s[l]; // 左指针右移，左指针指向的字符要被丢弃

            // 被舍弃的是目标字符，将其对应的缺失个数加一
            if (map[leftChar] !== undefined) map[leftChar]++;

            // 如果被舍弃的字符的缺失个数新变为正数，缺失的种类数加一
            if (map[leftChar] > 0) missingType++;

            l++; // 左指针右移，收缩窗口
        }
        r++; // 右指针右移，扩张窗口
    }

    // 如果最小窗口的起点仍然是 s 长度，说明没有找到符合条件的窗口，返回空字符串；否则，返回最小窗口子串
    return start == s.length ? "" : s.substring(start, start + minLen);
};