首页 > 试题广场 >

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

[编程题]最长不含重复字符的子字符串。
  • 热度指数：451 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解


请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例1

输入

"abcabcbb"

输出

3

说明

因为无重复字符的最长子串是"abc"，所以其长度为 3
示例2

输入

"pwwkew"

输出

3

说明

因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
示例3

输入

"ipalfish"

输出

7

说明

因为无重复字符的最长子串是"palfish"，所以其长度为 7。
算法知识视频讲解
添加回答
JavaScript
牛客772883394号头像 牛客772883394号
哈希表+双指针滑动窗口。时间复杂度o(n)，只遍历一次；空间复杂度o(1)，虽然用了哈希表，但是字符ASCII码0~127，也就是说哈希表最多存128个数据，这是个常数级别，可认为是o(1)。 
function lengthOfLongestSubstring( s ) {
    // write code here
    //1. 用一个map存储子字符串信息，key-字符，value-下标。
    //2. 滑动窗口，双指针，begin，end。再用一个变量maxLength记录最大长度。
    //3. end变量字符串，如果map中有重复字符，maxLength = max（maxLength，
    // end-begin），更新begin = max（begin， value+1）。
    //4. 更新map信息。
    //5. 最后再更新一次maxLength。
    const map = new Map();
    let begin = 0;
    let end = 0;
    let maxLength = 0;
    while (end < s.length) {
        const char = s.charAt(end);
        if (map.has(char)) {
            maxLength = Math.max(maxLength, end - begin);
            begin = Math.max(begin, map.get(char) + 1);
        }
        map.set(char, end);
        end++;
    }
    maxLength = Math.max(maxLength, end - begin);
    return maxLength;
}


发表于 2021-08-13 11:51:56 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 伴鱼少儿英语 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
1条回答 4532浏览

热门推荐

通过挑战的用户

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号