最长不含重复字符的子字符串

滑动窗口+哈希

  1. 解题思路：

    • 哈希表 dic 统计： 指针 j 遍历字符 s ，哈希表统计字符 s[j] 最后一次出现的索引；
    • 更新左指针 i： 根据上轮左指针 i 和 dic[s[j]]，每轮更新左边界 i ，保证区间 [i + 1, j] 内无重复字符且最大；
    • 更新结果 res： 取上轮 res 和本轮双指针区间 [i + 1,j] 的宽度（即 j - i）中的最大值；

  2. 图解：








  3. 复杂度：

    • 时间复杂度： O(N)，其中 N 为字符串长度；
    • 空间复杂度： O(1)，字符的 ASCII 码范围为 0 ~ 127，哈希表 dic 最多使用 O(128) = O(1)大小的额外空间；

  4. 代码实现：

    function lengthOfLongestSubstring(s: string): number {
    let res = 0;
    let dict = new Map; // 哈希

    for (let i = -1, j = 0; j < s.length; j++) {
        let c = s[j];
        // 遇到重复的字母，缩短窗口左边界（向右移动）
        if (dict.has(c)) i = Math.max(i, dict.get(c));

        dict.set(c, j); // 记录当前字母的索引
        res = Math.max(res, j - i);
    }
    return res;
};

动态规划+哈希

  1. 解题思路：

    • 遍历字符串 s 时，使用哈希表（记为 dic）统计各字符最后一次出现的索引位置；
    • 状态定义： 设动态规划列表 dp ，dp[j] 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度；
    • 转移方程： 固定右边界 j，设字符 s[j] 左边距离最近的相同字符为 s[i] ；
      • 当 i < 0，即 s[j] 左边无相同字符，则 dp[j] = dp[j-1] + 1；
      • 当 dp[j - 1] < j - i，说明字符 s[i] 在子字符串 dp[j-1] 区间之外 ，则 dp[j] = dp[j - 1] + 1；
      • 当 dp[j - 1] ≥j − i，说明字符 s[i] 在子字符串 dp[j-1] 区间之中 ，则 dp[j] 的左边界由 s[i] 决定，即 dp[j] = j - i；
    • 最后合并为：

  2. 图解：









  3. 复杂度：

    • 时间复杂度： O(N)，其中 N 为字符串长度；
    • 空间复杂度： O(1)，字符的 ASCII 码范围为 0 ~ 127，哈希表 dic 最多使用 O(128) = O(1)大小的额外空间；

  4. 代码实现：

    function lengthOfLongestSubstring(s: string): number {
    let res = 0;
    let dict = new Map; // 哈希
    let tmp = 0;
    let i = -1;

    for (let j = 0; j < s.length; j++) {
        if (dict.has(s[j])) {
            i = dict.get(s[j]); // 获取索引
        }
        dict.set(s[j], j); // 更新哈希表
        tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
        res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
    }

    return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 最长不含重复字符的子字符串
  2. 2. 滑动窗口+哈希
  3. 3. 动态规划+哈希