1.数组与字符串

1. 双指针法

1.思路

• 通过两个指针在数组或字符串上按照特定规则移动，解决诸如查找、匹配、计算等问题。指针的移动方向和条件取决于具体问题，可相向、同向移动等。

2.经典案例

LeetCode 11. 盛最多水的容器

• 在表示竖线高度的数组上，双指针分别指向数组两端，根据指针所指高度调整指针位置，计算并更新容器最大水量。

LeetCode 167. 两数之和 II - 输入有序数组

• 在有序数组中，利用双指针从两端开始移动，根据两指针所指元素和与目标值的关系，找到和为目标值的两个数。

2.滑动窗口法

1.思路

• 在字符串或数组上维护一个窗口，通过移动窗口的起始和结束位置，动态调整窗口内元素，以满足特定条件，如寻找特定子串、子数组等。窗口大小可固定或动态变化。

2.经典案例

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

• 在字符串上通过滑动窗口，确保窗口内无重复字符，从而找到最长无重复子串。

LeetCode 76. 最小覆盖子串

• 在字符串 s 上利用滑动窗口，先扩大窗口使其包含字符串 t 的所有字符，再缩小窗口找到覆盖 t 的最小子串。

3.前缀和法

1.思路

• 对数组进行预处理，生成一个前缀和数组，其中每个元素表示原数组从起始位置到该位置的元素之和。利用前缀和数组可以高效解决子数组求和、特定和的子数组计数等问题。

2.经典案例

LeetCode 303. 区域和检索 - 数组不可变

• 通过前缀和数组快速计算给定区间内的元素之和。

LeetCode 560. 和为 K 的子数组

• 借助前缀和数组，统计和为 K 的子数组的个数。

2.链表

1.双指针法（链表场景）

1.思路

• 在链表上使用两个指针，根据问题需求同步或异步移动指针，用于检测链表特性（如环）、查找特定节点等。

2.经典案例

• 在判断链表是否有环的问题中（类似 LeetCode 141. 环形链表），快慢指针同时移动，快指针每次移动两步，若快慢指针相遇则存在环。

3.树

1.深度优先搜索（DFS） - 递归实现

1.思路

• 沿着树的深度优先探索节点，先访问根节点，然后递归地访问左子树和右子树（对于二叉树）。可用于遍历树、计算节点值、查找特定节点等。

2.经典案例

• 在二叉树的前序遍历（LeetCode 144. 二叉树的前序遍历）中，先访问根节点，再递归前序遍历左子树，最后递归前序遍历右子树。

2.广度优先搜索（BFS） - 队列实现

1.思路

• 按树的层次逐层访问节点，使用队列辅助实现。先将根节点入队，每次从队列取出一个节点，访问它并将其孩子节点入队，直到队列为空。常用于按层遍历树、解决与层次相关的问题。

2.经典案例

• 在二叉树的层序遍历（LeetCode 102. 二叉树的层序遍历）中，通过队列实现按层访问二叉树的所有节点。

4.栈

1.单调栈法

1.思路

• 利用栈维护一个单调递增或递减的序列，通过入栈和出栈操作，解决寻找下一个更大元素、下一个更小元素等问题。

2.经典案例

LeetCode 496. 下一个更大元素 I

• 遍历数组，利用单调栈记录每个元素的下一个更大元素。

LeetCode 84. 柱状图中最大的矩形

• 通过单调栈维护柱子高度，计算柱状图中最大矩形面积。

5.堆

1.堆（优先队列）法

1.思路

• 利用堆的特性维护数据的优先级，通过插入和删除操作，解决前 K 个最大或最小元素、中位数等问题。

2.经典案例：

LeetCode 215. 数组中的第 K 个最大元素

• 使用最小堆获取数组中第 K 个最大元素。

LeetCode 347. 前 K 个高频元素

• 结合哈希表统计频率，利用优先队列（最大堆）获取前 K 个高频元素。

6.通用的算法策略

1.二分查找法

适用场景

• 主要用于有序数组或可转化为有序结构的场景。

算法思路

• 每次将搜索区间缩小一半，通过比较中间元素与目标值的大小关系，决定在左半部分还是右半部分继续搜索，从而快速定位目标元素或满足特定条件的位置。

经典案例

LeetCode 704. 二分查找

• 在有序数组中查找目标值，每次比较中间元素与目标值，缩小搜索范围，直到找到目标值或确定目标值不存在。

LeetCode 33. 搜索旋转排序数组

• 对于旋转排序数组，通过判断中间元素与两端元素的关系，确定有序部分，然后在有序部分进行二分查找。

2.动态规划法

适用场景

• 适用于具有最优子结构和子问题重叠性质的问题，可用于数组、字符串、图等多种数据结构相关问题。

算法思路

• 将复杂问题分解为相互关联的子问题，通过定义状态和状态转移方程，求解子问题并保存其解，避免重复计算，最终得到原问题的解。

经典案例

LeetCode 5. 最长回文子串

• 定义二维状态 dp [i][j] 表示字符串 s 从 i 到 j 是否为回文串，通过状态转移方程和边界条件计算最长回文子串。

LeetCode 70. 爬楼梯

• 定义状态 dp [i] 表示爬到第 i 阶楼梯的方法数，依据状态转移方程和边界条件计算爬到楼顶的方法总数。

3.回溯法

适用场景

• 常用于解决组合、排列、路径搜索等问题，涉及对所有可能情况进行深度优先搜索。

算法思路

• 从初始状态开始，逐步探索所有可能路径。若当前路径不符合要求，则回溯到上一个状态，尝试其他路径，直到找到所有解或满足条件的解。

经典案例

LeetCode 46. 全排列

• 从空排列开始，通过回溯依次添加未使用数字，生成所有全排列。

LeetCode 93. 复原 IP 地址

• 通过在字符串中回溯插入点，将字符串分成 4 段，判断每段合法性，得到所有有效 IP 地址。

4.贪心算法

适用场景

• 适用于具有贪心选择性质的问题，即局部最优选择能导致全局最优解，常见于资源分配、调度等问题。

算法思路

• 在每一步决策中，选择当前状态下的最优解，不考虑整体最优解，期望通过一系列局部最优选择达到全局最优。

经典案例

LeetCode 455. 分发饼干

• 对孩子胃口值和饼干尺寸排序后，从胃口最小孩子和尺寸最小饼干开始匹配，每次选择能满足当前孩子的最小饼干。

LeetCode 122. 买卖股票的最佳时机 II

• 每天判断当前价格与前一天价格，若当前价格高则进行买卖操作累加利润。

5.分治法

适用场景

• 适用于可以分解为若干个规模较小、相互独立且与原问题形式相同的子问题的场景，如树的相关问题、数组划分问题等。

算法思路

• 将问题分解为子问题，递归地解决子问题，然后合并子问题的解得到原问题的解。

经典案例

LeetCode 241. 为运算表达式设计优先级

• 按运算符分割表达式为左右两部分，递归计算左右部分结果，再根据运算符组合结果。

LeetCode 53. 最大子数组和

• 将数组分成左右两部分，分别计算左右部分最大子数组和以及跨越中点的最大子数组和，取三者最大值。

正则表达式匹配

1.题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

示例 1：

输入： s = "aa", p = "a"
输出： false
解释： "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入： s = "aa", p = "a*"
输出： true
解释： 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入： s = "ab", p = ".*"
输出： true
解释： ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

2.解决方案

1.暴力递归解法

1. 思路：

• 从字符串 s 和模式 p 的开头开始匹配。

• 对于模式 p 中的每个字符，分情况讨论：

  • 如果 p 的当前字符不是 '*'，那么 s 和 p 当前字符必须匹配（s 当前字符存在且与 p 当前字符相等或者 p 当前字符为 '.'），然后继续匹配下一个字符。

  • 如果 p 的当前字符是 '*'，则有两种情况：

    • '*' 前面的字符匹配 0 次，此时跳过 p 中 '*' 及其前面的字符，继续匹配 p 的下一个字符。
    • '*' 前面的字符匹配至少 1 次，前提是 s 当前字符与 '*' 前面的字符匹配（s 当前字符存在且与 '*' 前面的字符相等或者 '*' 前面的字符为 '.'），然后 s 指针后移一位，继续尝试匹配。

  • 当 s 和 p 都匹配完时，返回 true；否则，返回 false。

2. 代码实现：

function isMatch(s: string, p: string): boolean {
    if (!p) return!s;
    let firstMatch = s && (s[0] === p[0] || p[0] === '.');
    if (p.length >= 2 && p[1] === '*') {
        return isMatch(s, p.slice(2)) || (firstMatch && isMatch(s.slice(1), p));
    } else {
        return firstMatch && isMatch(s.slice(1), p.slice(1));
    }
}

3. 分析：

• 时间复杂度：在最坏情况下，时间复杂度为指数级 (O(2^{m + n}))，其中 m 和 n 分别是 s 和 p 的长度。因为对于每个字符，都可能有两种决策（'*' 的两种情况）。
• 空间复杂度：(O(m + n))，这是由于递归调用栈的深度最大为 m + n。

4. 缺点：

• 时间复杂度高，对于较长的字符串和模式，效率极低，容易超时。

2.动态规划解法

1. 思路：

• 使用一个二维数组 dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。

• 初始化 dp[0][0] = true，表示两个空字符串是匹配的。

• 对于 dp[i][j] 的计算：

• 如果 p[j - 1] 不是 '*'，那么 dp[i][j] 为 true 当且仅当 dp[i - 1][j - 1] 为 true 且 s[i - 1] 与 p[j - 1] 匹配（s[i - 1] 存在且与 p[j - 1] 相等或者 p[j - 1] 为 '.'）。

  • 如果 p[j - 1] 是 '*'，则有两种情况：

    • '*' 前面的字符匹配 0 次，此时 dp[i][j] = dp[i][j - 2]。
    • '*' 前面的字符匹配至少 1 次，前提是 s[i - 1] 与 p[j - 2] 匹配（s[i - 1] 存在且与 p[j - 2] 相等或者 p[j - 2] 为 '.'），此时 dp[i][j] = dp[i - 1][j]。

2. 代码实现：

function isMatch(s: string, p: string): boolean {
    const m = s.length;
    const n = p.length;
    const dp: boolean[][] = new Array(m + 1).fill(false).map(() => new Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2];
                if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }
    return dp[m][n];
}

3. 分析：

• 时间复杂度：(O(m * n))，其中 m 和 n 分别是 s 和 p 的长度。需要填充整个 dp 数组。
• 空间复杂度：(O(m * n))，用于存储 dp 数组。可以通过滚动数组优化到 (O(n))，因为 dp[i][j] 只依赖于 dp[i - 1][j] 和 dp[i][j - 1] 以及 dp[i - 1][j - 1]。

4. 优点：

• 相比暴力递归，时间复杂度大大降低，对于较长的字符串和模式，效率更高。

3.最优解及原因

1. 最优解：

• 动态规划解法是最优解。

2. 原因：

• 动态规划解法通过避免重复计算子问题，将时间复杂度从暴力递归的指数级 (O(2^{m + n})) 降低到 (O(m * n))。虽然空间复杂度也为 (O(m * n))，但在实际应用中，其效率的提升更为显著。滚动数组优化后的空间复杂度可进一步降低到 (O(n))，使得在处理长字符串时更具优势。

最长回文子串

1.题目描述

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

输入： s = "babad"
输出： "bab"
解释： "aba" 同样是符合题意的答案。

示例 2：

输入： s = "cbbd"
输出： "bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

2.解决方案

1.暴力解法

1. 思路：

• 枚举字符串 s 的所有子串，对于每个子串，检查它是否是回文串。
• 从长度为 1 的子串开始，逐渐增加子串长度，记录下最长的回文子串。

2. 代码实现：

function longestPalindromeBruteForce(s: string): string {
    let maxLength = 0;
    let result = '';
    const n = s.length;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            let isPalindrome = true;
            for (let k = 0; k < (j - i + 1) / 2; k++) {
                if (s[i + k]!== s[j - k]) {
                    isPalindrome = false;
                    break;
                }
            }
            if (isPalindrome && (j - i + 1) > maxLength) {
                maxLength = j - i + 1;
                result = s.slice(i, j + 1);
            }
        }
    }
    return result;
}

3. 分析：

• 时间复杂度：(O(n^3))。外层循环遍历子串的起始位置 i，时间复杂度为 (O(n))；中层循环遍历子串的结束位置 j，时间复杂度为 (O(n))；内层循环检查子串是否为回文，时间复杂度为 (O(n))。所以总的时间复杂度为 (O(n \times n \times n))。
• 空间复杂度：(O(1))，除了存储结果的字符串外，只使用了常数级别的额外空间。

4. 缺点：时间复杂度极高，对于较长的字符串，运行效率极低，会导致超时。

2.中心扩展算法

1. 思路：

• 回文串的特点是关于中心对称，所以可以以每个字符和相邻字符间隙为中心，向两边扩展，检查扩展出的子串是否为回文。
• 对于长度为 n 的字符串，有 2n - 1 个可能的中心（n 个字符作为单字符中心，n - 1 个相邻字符间隙作为双字符中心）。

2. 代码实现：

function longestPalindrome(s: string): string {
    let start = 0;
    let maxLength = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        // 以单个字符为中心扩展
        let left1 = i;
        let right1 = i;
        while (left1 >= 0 && right1 < n && s[left1] === s[right1]) {
            if (right1 - left1 + 1 > maxLength) {
                maxLength = right1 - left1 + 1;
                start = left1;
            }
            left1--;
            right1++;
        }
        // 以两个相邻字符为中心扩展
        let left2 = i;
        let right2 = i + 1;
        while (left2 >= 0 && right2 < n && s[left2] === s[right2]) {
            if (right2 - left2 + 1 > maxLength) {
                maxLength = right2 - left2 + 1;
                start = left2;
            }
            left2--;
            right2++;
        }
    }
    return s.slice(start, start + maxLength);
}

3. 分析：

• 时间复杂度：(O(n^2))。对于每个可能的中心，最多需要扩展 n 次，而总共有 2n - 1 个中心，所以时间复杂度为 (O(n \times n))。
• 空间复杂度：(O(1))，只使用了常数级别的额外空间。

4. 优点：相比暴力解法，时间复杂度有所降低，在实际应用中效率更高。

3.Manacher 算法

1. 思路：

• Manacher 算法通过对字符串进行预处理，将奇数长度和偶数长度的回文串统一处理。
• 它利用已经计算出的回文子串信息，避免了重复计算，从而将时间复杂度优化到 (O(n))。
• 具体来说，算法使用一个数组 p 记录以每个字符为中心的回文半径，通过巧妙的计算和更新，快速找到最长回文子串。

2. 代码实现：

function longestPalindromeManacher(s: string): string {
    // 预处理字符串
    const newS = '#';
    for (const char of s) {
        newS += char + '#';
    }
    const n = newS.length;
    const p: number[] = new Array(n).fill(0);
    let center = 0;
    let right = 0;
    for (let i = 0; i < n; i++) {
        let iMirror = 2 * center - i;
        if (right > i) {
            p[i] = Math.min(right - i, p[iMirror]);
        } else {
            p[i] = 0;
        }
        // 尝试扩展
        while (i + (1 + p[i]) < n && i - (1 + p[i]) >= 0 && newS[i + (1 + p[i])] === newS[i - (1 + p[i])]) {
            p[i]++;
        }
        // 更新中心和右边界
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    let maxLen = 0;
    let maxCenter = 0;
    for (let i = 0; i < n; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenter = i;
        }
    }
    const start = (maxCenter - maxLen) / 2;
    return s.slice(start, start + maxLen);
}

3. 分析：

• 时间复杂度：(O(n))。虽然代码中有多层循环，但由于巧妙地利用了已有的回文信息，每个字符最多被访问常数次，所以时间复杂度为 (O(n))。
• 空间复杂度：(O(n))，需要一个数组 p 来记录回文半径。

4. 优点：时间复杂度最优，在处理非常长的字符串时，性能远远优于暴力解法和中心扩展算法。

4.最优解及原因

1. 最优解：Manacher 算法是最优解。
2. 原因：当字符串长度较大时，时间复杂度是衡量算法优劣的关键指标。Manacher 算法将时间复杂度优化到了线性的 (O(n))，相比暴力解法的 (O(n^3)) 和中心扩展算法的 (O(n^2))，在处理大规模数据时效率有显著提升。虽然它需要 (O(n)) 的额外空间，但对于追求高效的场景，这种以空间换时间的方式是值得的。

3.拓展和题目变形

拓展：

• 找到所有最长回文子串。

思路：

• 在 Manacher 算法的基础上，记录所有达到最大回文半径的中心位置，然后根据这些位置还原出所有最长回文子串。

代码实现：

function findAllLongestPalindromes(s: string): string[] {
    const newS = '#';
    for (const char of s) {
        newS += char + '#';
    }
    const n = newS.length;
    const p: number[] = new Array(n).fill(0);
    let center = 0;
    let right = 0;
    for (let i = 0; i < n; i++) {
        let iMirror = 2 * center - i;
        if (right > i) {
            p[i] = Math.min(right - i, p[iMirror]);
        } else {
            p[i] = 0;
        }
        while (i + (1 + p[i]) < n && i - (1 + p[i]) >= 0 && newS[i + (1 + p[i])] === newS[i - (1 + p[i])]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    let maxLen = 0;
    const maxCenters: number[] = [];
    for (let i = 0; i < n; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenters.length = 0;
            maxCenters.push(i);
        } else if (p[i] === maxLen) {
            maxCenters.push(i);
        }
    }
    const results: string[] = [];
    for (const maxCenter of maxCenters) {
        const start = (maxCenter - maxLen) / 2;
        results.push(s.slice(start, start + maxLen));
    }
    return results;
}

题目变形：

• 给定一个字符串 s 和一个整数 k，找到长度至少为 k 的最长回文子串。

思路：

• 可以在中心扩展算法或 Manacher 算法的基础上进行修改。在扩展或计算回文半径时，当找到的回文子串长度达到或超过 k 时，记录下来并继续寻找更长的满足条件的回文子串。

代码实现（基于中心扩展算法） ：

function longestPalindromeWithMinLength(s: string, k: number): string {
    let start = 0;
    let maxLength = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        let left1 = i;
        let right1 = i;
        while (left1 >= 0 && right1 < n && s[left1] === s[right1]) {
            if (right1 - left1 + 1 >= k && right1 - left1 + 1 > maxLength) {
                maxLength = right1 - left1 + 1;
                start = left1;
            }
            left1--;
            right1++;
        }
        let left2 = i;
        let right2 = i + 1;
        while (left2 >= 0 && right2 < n && s[left2] === s[right2]) {
            if (right2 - left2 + 1 >= k && right2 - left2 + 1 > maxLength) {
                maxLength = right2 - left2 + 1;
                start = left2;
            }
            left2--;
            right2++;
        }
    }
    return maxLength >= k? s.slice(start, start + maxLength) : '';
}

寻找两个正序数组的中位数

1. 题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1,2,3] ，中位数 2

示例 2：

输入： nums1 = [1,2], nums2 = [3,4]
输出： 2.50000
解释： 合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

2. 解决方案

1. 合并数组后找中位数

1. 思路：

• 首先将两个有序数组合并成一个新的有序数组。
• 然后根据新数组的长度是奇数还是偶数来计算中位数。如果新数组长度 len 是奇数，中位数就是新数组第 Math.floor(len / 2) 个元素；如果 len 是偶数，中位数就是新数组第 len / 2 - 1 个元素和第 len / 2 个元素的平均值。

2. 代码实现：

function findMedianSortedArraysMerge(nums1: number[], nums2: number[]): number {
    const merged: number[] = [];
    let i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            merged.push(nums1[i]);
            i++;
        } else {
            merged.push(nums2[j]);
            j++;
        }
    }
    while (i < nums1.length) {
        merged.push(nums1[i]);
        i++;
    }
    while (j < nums2.length) {
        merged.push(nums2[j]);
        j++;
    }
    const len = merged.length;
    if (len % 2 === 1) {
        return merged[Math.floor(len / 2)];
    } else {
        return (merged[len / 2 - 1] + merged[len / 2]) / 2;
    }
}

3. 分析：

• 时间复杂度：(O(m + n))，因为需要遍历两个数组一次，将它们合并。
• 空间复杂度：(O(m + n))，需要创建一个大小为 m + n 的新数组来存储合并后的结果。

4. 优点：

• 思路简单直接，容易理解和实现，对于初学者来说是比较容易想到的方法。

5. 缺点：

• 空间复杂度较高，需要额外的空间来存储合并后的数组。如果两个数组非常大，可能会导致内存问题。

2. 二分查找法（优化解法）

1. 思路：

• 目标是将两个数组合并后找到中位数，我们可以通过二分查找的方式，在不实际合并数组的情况下找到中位数。
• 假设两个数组分别为 nums1 和 nums2，长度分别为 m 和 n。我们将两个数组划分为两部分，使得左半部分的所有元素都小于等于右半部分的所有元素。
• 通过二分查找在较短的数组（假设为 nums1）上进行，确定一个划分点 i，同时根据总长度计算出另一个数组 nums2 的划分点 j = (m + n + 1) / 2 - i。
• 然后检查划分是否满足条件：nums1[i - 1] <= nums2[j] 且 nums2[j - 1] <= nums1[i]。如果满足，根据数组总长度的奇偶性计算中位数；如果不满足，调整划分点 i 继续查找。

2. 代码实现：

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    const m = nums1.length;
    const n = nums2.length;
    let low = 0, high = m;
    while (low <= high) {
        const i = Math.floor((low + high) / 2);
        const j = Math.floor((m + n + 1) / 2) - i;
        const maxLeft1 = i === 0? -Infinity : nums1[i - 1];
        const minRight1 = i === m? Infinity : nums1[i];
        const maxLeft2 = j === 0? -Infinity : nums2[j - 1];
        const minRight2 = j === n? Infinity : nums2[j];
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((m + n) % 2 === 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    return 0;
}

3. 分析：

• 时间复杂度：(O(log(min(m, n))))，因为二分查找是在较短的数组上进行的，每次迭代都将搜索区间减半。
• 空间复杂度：(O(1))，只需要几个指针和变量来辅助计算，不需要额外的数组空间。

4. 优点：

• 时间复杂度较低，在处理大规模数据时效率更高。空间复杂度为常数级别，大大节省了内存。

5. 缺点：

• 算法思路相对复杂，代码实现难度较大，需要对二分查找和数组划分有较深入的理解。

3. 最优解及原因

1. 最优解：二分查找法是最优解。
2. 原因：二分查找法在时间复杂度和空间复杂度上都优于合并数组后找中位数的方法。在处理大规模数据时，其 (O(log(min(m, n)))) 的时间复杂度能够显著提高算法效率，并且 (O(1)) 的空间复杂度使得它在内存使用上非常高效。虽然实现相对复杂，但对于追求高性能的场景，这种方法是最合适的。

3. 拓展和题目变形

拓展：

• 如果数组不是有序的，如何找到两个数组合并后的中位数？

思路：

• 首先对两个数组进行排序，然后可以使用合并数组后找中位数的方法或者二分查找法来求解。排序可以使用高效的排序算法，如快速排序或归并排序，时间复杂度为 (O((m + n)log(m + n)))。
• 另一种方法是使用两个堆（一个最大堆和一个最小堆）来维护数据流，在插入元素的同时保持堆的平衡，使得两个堆的元素个数满足一定关系，从而可以快速找到中位数。每次插入元素的时间复杂度为 (O(log(m + n)))，最终获取中位数的时间复杂度为 (O(1))。

代码实现（使用堆） ：

import { MaxPriorityQueue, MinPriorityQueue } from '@datastructures-js/priority-queue';
function findMedianUnsortedArrays(nums1: number[], nums2: number[]): number {
    const maxHeap = new MaxPriorityQueue();
    const minHeap = new MinPriorityQueue();
    const allNums = [...nums1, ...nums2];
    for (const num of allNums) {
        if (maxHeap.size() === 0 || num <= maxHeap.front()) {
            maxHeap.enqueue(num);
        } else {
            minHeap.enqueue(num);
        }
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.enqueue(maxHeap.dequeue()!.element);
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.enqueue(minHeap.dequeue()!.element);
        }
    }
    if (maxHeap.size() === minHeap.size()) {
        return (maxHeap.front() + minHeap.front()) / 2;
    } else {
        return maxHeap.front();
    }
}

题目变形：

• 给定三个正序数组，找到这三个数组合并后的中位数。

思路：

• 可以将其扩展为类似于两个数组的二分查找方法。先在其中一个较短的数组上进行二分查找确定划分点，然后根据总长度和其他两个数组的划分点关系来确定其他数组的划分点，再检查划分是否满足条件，不断调整划分点直到找到中位数。
• 也可以先将三个数组合并为一个有序数组（时间复杂度为 (O(m + n + p))，其中 m, n, p 分别为三个数组的长度），然后按照常规方法找中位数。

代码实现（扩展二分查找） ：

function findMedianOfThreeSortedArrays(nums1: number[], nums2: number[], nums3: number[]): number {
    const totalLength = nums1.length + nums2.length + nums3.length;
    const isEven = totalLength % 2 === 0;
    const halfLength = Math.floor(totalLength / 2);
    if (nums1.length > nums2.length) {
        return findMedianOfThreeSortedArrays(nums2, nums1, nums3);
    }
    if (nums1.length > nums3.length) {
        return findMedianOfThreeSortedArrays(nums3, nums2, nums1);
    }
    let low = 0, high = nums1.length;
    while (low <= high) {
        const i = Math.floor((low + high) / 2);
        const remainingLength = halfLength - i;
        const j = Math.max(0, Math.min(nums2.length, remainingLength));
        const k = remainingLength - j;
        const maxLeft1 = i === 0? -Infinity : nums1[i - 1];
        const minRight1 = i === nums1.length? Infinity : nums1[i];
        const maxLeft2 = j === 0? -Infinity : nums2[j - 1];
        const minRight2 = j === nums2.length? Infinity : nums2[j];
        const maxLeft3 = k === 0? -Infinity : nums3[k - 1];
        const minRight3 = k === nums3.length? Infinity : nums3[k];
        if (maxLeft1 <= minRight2 && maxLeft1 <= minRight3 && maxLeft2 <= minRight1 && maxLeft2 <= minRight3 && maxLeft3 <= minRight1 && maxLeft3 <= minRight2) {
            if (isEven) {
                return (Math.max(maxLeft1, maxLeft2, maxLeft3) + Math.min(minRight1, minRight2, minRight3)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2, maxLeft3);
            }
        } else if (maxLeft1 > minRight2 || maxLeft1 > minRight3) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    return 0;
}

无重复字符的最长子串

1. 题目描述

给定一个字符串 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 由英文字母、数字、符号和空格组成

2. 解决方案

暴力解法

1. 思路：

• 枚举字符串 s 的所有子串，对于每个子串，检查其是否包含重复字符。
• 从长度为 1 的子串开始，逐渐增加子串长度，记录下不包含重复字符的最长子串的长度。

2. 代码实现：

function lengthOfLongestSubstringBruteForce(s: string): number {
    let maxLength = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            const subStr = s.slice(i, j + 1);
            const charSet = new Set();
            let isDuplicate = false;
            for (const char of subStr) {
                if (charSet.has(char)) {
                    isDuplicate = true;
                    break;
                }
                charSet.add(char);
            }
            if (!isDuplicate) {
                maxLength = Math.max(maxLength, subStr.length);
            }
        }
    }
    return maxLength;
}

3. 分析：

• 时间复杂度：(O(n^3))。外层循环遍历子串的起始位置 i，时间复杂度为 (O(n))；内层循环遍历子串的结束位置 j，时间复杂度为 (O(n))；对于每个子串，检查是否有重复字符需要遍历子串中的每个字符，时间复杂度为 (O(n))。所以总的时间复杂度为 (O(n \times n \times n))。
• 空间复杂度：(O(min(n, m)))，其中 n 是字符串 s 的长度，m 是字符集的大小。在最坏情况下，子串中包含所有不同字符，此时空间复杂度为 (O(n))；如果字符集大小有限，如 ASCII 字符集大小为 128，则空间复杂度为 (O(m))。

4. 缺点：时间复杂度非常高，在处理较长字符串时，运行效率极低，会导致超时。

滑动窗口解法

1. 思路：

• 使用滑动窗口来维护一个不包含重复字符的子串。
• 用一个集合（Set）来记录当前窗口内的字符。
• 初始化窗口的左右边界 left 和 right 都为 0。
• 移动右边界 right，将新字符加入集合。如果新字符已在集合中，说明出现重复，移动左边界 left，并从集合中移除相应字符，直到窗口内不再有重复字符。
• 每次移动后，更新最长无重复字符子串的长度。

2. 代码实现：

function lengthOfLongestSubstring(s: string): number {
    const charSet = new Set();
    let left = 0;
    let maxLength = 0;
    for (let right = 0; right < s.length; right++) {
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

3. 分析：

• 时间复杂度：(O(n))。虽然有一个嵌套的 while 循环，但 left 和 right 指针最多各移动 n 次，所以总的时间复杂度为 (O(n))。
• 空间复杂度：(O(min(n, m)))，与暴力解法相同，取决于字符串长度 n 和字符集大小 m。

4. 优点：时间复杂度大大降低，相比于暴力解法，在处理长字符串时效率有显著提升。

优化的滑动窗口解法（使用数组替代集合）

1. 思路：

• 如果字符串只包含 ASCII 字符（共 128 个），可以使用一个长度为 128 的数组来替代 Set 记录字符出现的位置。
• 数组的索引对应字符的 ASCII 码值，数组的值记录该字符上次出现的位置。
• 移动右边界时，检查当前字符上次出现的位置是否在当前窗口内，如果在，则更新左边界。

2. 代码实现：

function lengthOfLongestSubstringOptimized(s: string): number {
    const charIndex = new Array(128).fill(-1);
    let left = 0;
    let maxLength = 0;
    for (let right = 0; right < s.length; right++) {
        left = Math.max(left, charIndex[s.charCodeAt(right)] + 1);
        charIndex[s.charCodeAt(right)] = right;
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

3. 分析：

• 时间复杂度：(O(n))。与普通滑动窗口解法相同，left 和 right 指针最多各移动 n 次。
• 空间复杂度：(O(m))，这里 m 是固定的 128，因为使用了一个固定大小的数组。相比使用 Set，在空间上更优。

最优解及原因

1. 最优解：优化的滑动窗口解法（使用数组替代集合）是最优解。
2. 原因：它在时间复杂度上与普通滑动窗口解法相同，都是 (O(n))，但在空间复杂度上，对于只包含 ASCII 字符的字符串，它使用固定大小的数组，空间复杂度为 (O(m))（m = 128），优于普通滑动窗口解法的 (O(min(n, m)))。同时，数组的访问和更新操作比 Set 的操作在某些情况下效率更高。

3. 拓展和题目变形

拓展：

• 找到所有不含有重复字符的最长子串。

思路：

• 在滑动窗口的基础上，每次更新最长子串长度时，将符合长度的子串记录下来。

代码实现：

function findAllLongestSubstrings(s: string): string[] {
    const charIndex = new Array(128).fill(-1);
    let left = 0;
    let maxLength = 0;
    const result: string[] = [];
    for (let right = 0; right < s.length; right++) {
        left = Math.max(left, charIndex[s.charCodeAt(right)] + 1);
        charIndex[s.charCodeAt(right)] = right;
        if (right - left + 1 === maxLength) {
            result.push(s.slice(left, right + 1));
        } else if (right - left + 1 > maxLength) {
            maxLength = right - left + 1;
            result.length = 0;
            result.push(s.slice(left, right + 1));
        }
    }
    return result;
}

题目变形：

• 给定一个字符串 s 和一个整数 k，找到最长的包含不超过 k 个不同字符的子串。

思路：

• 使用滑动窗口，用一个对象记录窗口内不同字符的出现次数，当窗口内不同字符数超过 k 时，移动左边界，更新最长子串长度。

代码实现：

function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
    const charCount: { [key: string]: number } = {};
    let left = 0;
    let maxLength = 0;
    for (let right = 0; right < s.length; right++) {
        charCount[s[right]] = (charCount[s[right]] || 0) + 1;
        while (Object.keys(charCount).length > k) {
            charCount[s[left]]--;
            if (charCount[s[left]] === 0) {
                delete charCount[s[left]];
            }
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

两数相加

1. 题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [7,0,8]
解释： 342 + 465 = 807.

示例 2：

输入： l1 = [0], l2 = [0]
输出： [0]

示例 3：

输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出： [8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

2. 解决方案

1. 常规链表遍历解法

1. 思路：

• 同时遍历两个链表，从表头开始，将对应节点的值相加，并考虑进位。
• 创建一个新的链表来存储相加的结果。
• 遍历过程中，如果一个链表先遍历完，另一个链表剩余部分继续参与计算，同时处理进位情况直到所有节点遍历完且没有进位。

2. 代码实现：

// 定义链表节点类
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined? 0 : val);
        this.next = (next === undefined? null : next);
    }
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let dummyHead = new ListNode();
    let p = l1, q = l2, current = dummyHead;
    let carry = 0;

    while (p!== null || q!== null) {
        let x = p? p.val : 0;
        let y = q? q.val : 0;
        let sum = carry + x + y;
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;
        if (p) p = p.next;
        if (q) q = q.next;
    }

    if (carry > 0) {
        current.next = new ListNode(carry);
    }

    return dummyHead.next;
}

3. 分析：

• 时间复杂度：(O(max(m, n)))，其中 m 和 n 分别是两个链表的长度。因为我们需要遍历两个链表的最长者。
• 空间复杂度：(O(max(m, n)))，新链表的长度最大为较长链表的长度加 1（考虑进位）。

4. 优点：

• 思路直接明了，易于理解和实现。按照链表相加的实际逻辑进行处理，符合人类计算加法的思维方式。

5. 缺点：

• 没有对链表的遍历和计算过程进行特殊优化，对于非常长的链表，可能在性能上存在一定瓶颈。

2. 递归解法

1. 思路：

• 递归地处理链表节点的相加。每次递归处理当前两个节点的和以及进位。
• 递归的终止条件是两个链表都为空且没有进位。

2. 代码实现：

function addTwoNumbersRecursive(l1: ListNode | null, l2: ListNode | null, carry = 0): ListNode | null {
    if (!l1 &&!l2 &&!carry) {
        return null;
    }

    let sum = carry;
    sum += l1? l1.val : 0;
    sum += l2? l2.val : 0;

    let newNode = new ListNode(sum % 10);
    newNode.next = addTwoNumbersRecursive(
        l1 && l1.next,
        l2 && l2.next,
        Math.floor(sum / 10)
    );

    return newNode;
}

3. 分析：

• 时间复杂度：(O(max(m, n)))，同样需要遍历两个链表的最长者。
• 空间复杂度：(O(max(m, n)))，递归调用栈的深度最大为较长链表的长度加 1（考虑进位）。

4. 优点：

• 代码简洁，递归的方式能够很好地体现链表结构的递归特性，使代码更具逻辑性和可读性。

5. 缺点：

• 递归调用会消耗额外的栈空间，对于非常长的链表，可能导致栈溢出问题。相比迭代解法，性能上在某些情况下可能稍逊一筹。

3. 最优解及原因

1. 最优解：常规链表遍历（迭代）解法是更优选择。
2. 原因：虽然两种解法时间复杂度相同，但迭代解法在空间使用上更为稳定，不会因为递归调用而产生栈溢出风险，尤其是在处理非常长的链表时，迭代解法更加可靠。

3.拓展和题目变形

拓展

• 如果链表中的数字是正序存储（即最高位在链表头部），如何解决？

思路：

• 一种方法是先将链表反转，然后按照现有方式相加，最后再将结果链表反转。
• 另一种更高效的方法是使用栈来存储链表节点的值，因为栈可以实现后进先出，从而模拟逆序相加的过程。

代码实现（使用栈） ：

function addTwoNumbersForward(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let stack1: number[] = [];
    let stack2: number[] = [];

    while (l1) {
        stack1.push(l1.val);
        l1 = l1.next;
    }

    while (l2) {
        stack2.push(l2.val);
        l2 = l2.next;
    }

    let carry = 0;
    let result: ListNode | null = null;

    while (stack1.length > 0 || stack2.length > 0 || carry > 0) {
        let sum = carry;
        sum += stack1.length > 0? stack1.pop()! : 0;
        sum += stack2.length > 0? stack2.pop()! : 0;

        carry = Math.floor(sum / 10);
        let newNode = new ListNode(sum % 10);
        newNode.next = result;
        result = newNode;
    }

    return result;
}

题目变形：

• 如果链表中的节点值可以是负数，如何处理？

思路：

• 在计算节点值之和时，直接按照整数运算规则处理负数。
• 处理进位时需要注意，当和为负数时，需要将进位调整为 -1，同时节点值加上 10（例如 -2 可表示为 -1 进位和 8 节点值）。

代码实现：

function addTwoNumbersWithNegative(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let dummyHead = new ListNode();
    let p = l1, q = l2, current = dummyHead;
    let carry = 0;

    while (p!== null || q!== null) {
        let x = p? p.val : 0;
        let y = q? q.val : 0;
        let sum = carry + x + y;
        if (sum < 0) {
            carry = -1;
            sum += 10;
        } else {
            carry = Math.floor(sum / 10);
        }
        current.next = new ListNode(sum % 10);
        current = current.next;
        if (p) p = p.next;
        if (q) q = q.next;
    }

    if (carry!== 0) {
        current.next = new ListNode(carry);
    }

    return dummyHead.next;
}