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

lily_wang 发布于2019-08-23 14:17 / 1066人阅读

摘要：题目给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例输入输出解释因为无重复字符的最长子串是，所以其长度为。

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

示例 1:

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

示例 2:

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

示例 3:

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

 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解答：
1.暴力破解

var lengthOfLongestSubstring = function(s) {
    var l = s.length;
    var re = 0;
    for (var i= 0; i < l; i++) { //1
        for(var j = i + 1; j <= l; j++){ //2
           if(check(i, j)) {
               re = Math.max(re, j - i)
           } else {
               break
           }
        }
    }
    function check(start, end) {
        var a  = [];
        for (var k = start; k < end; k++) { //3
            if (a.indexOf(s[k]) !== -1) {
                return false
            } else {
                a.push(s[k])
            }
        }
        return true;
    }
    return re
};

上来就是一顿for循环操作，这样暴力写我们的leetcode肯定是不会给过的，因为遇到超级长的字符串测试用例，执行时间会超出时间限制，上面代码的优化空间很大。
理一下逻辑，我们每次在2里面检测出有重复的字符时，记录这个重复字符前一次出现的位置index，然后中断这次循环，开始下一次1的循环，并且i的位置应该为index+1。

比如在i=0的时，在2循环里j=4时就会出现重复的字符d，字符d前一次出现的位置是1，这时最长字符串长度是4，并且被记录，这时应该开始1循环的下一次循环，并且是从i=2开始。
3循环和2循环其实是不必要的，我们创建一个动态的字符串，把每次循环到的字符加进去并实时记录它的长度，遇到重复的字符串就砍掉字符第一次出现跟它之前的字符串，比如上图，i循环到4时，出现重复字符d,d在之前出现的位置是1，我们应该砍掉动态字符串位置1跟它之前的字符串，来保证它是无重复的字符串。代码如下

var lengthOfLongestSubstring = function(s) {
    var l = s.length;
    var re = 0;
    var a = "", index;
    for (var i = 0; i < l; i++) {
        index = a.indexOf(s[i])
        if (index !== -1) {
            a = a.slice(index + 1)
        }
        a+=s[i]
        re = Math.max(re, a.length);
        
    }

    return re
};

一下从矮穷挫变成高富帅，速度杠杠哒！

GPU云服务器云服务器最长公共子串 java最长相同子串字符串找子串算法字符串最大子串c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100402.html

前端中等算法-无重复字符的最长子串

摘要：无重复字符的最长子串难度中等描述给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。输入输出解释因为无重复字符的最长子串是，所以其长度为。无重复字符的最长子串难度：中等描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。样例：输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。输入: bbbbb ...

hyuan 2019-08-26 10:40 评论0 收藏0
LeetCode3.无重复字符的最长子串JavaScript

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。 LeetCode3.无重复字符的最长子串JavaScript 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: abcabcbb输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2: 输入: bbbbb输出...

vboy1010 2019-08-23 14:46 评论0 收藏0
【leetcode】3. 无重复字符的最长子串

摘要：示例输入输出解释因为无重复字符的最长子串是，所以其长度为。请注意，你的答案必须是子串的长度，是一个子序列，不是子串。完成循环后取队列中出现的最大长度即可。给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1：输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。示例 2：输入: bbbbb 输出: 1 解释:...

qc1iu 2019-08-23 18:32 评论0 收藏0
LeetCode.3 无重复字符的最长子串(JS)

摘要：先跳到第三题是因为第二题第一眼没读懂一题目无重复字符的最长子串给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例输入输出解释因为无重复字符的最长子串是，所以其长度为。以此来实现判断是否包含重复字符。先跳到第三题是因为第二题第一眼没读懂一、题目无重复字符的最长子串：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例1 输入: abcabcbb输...

wthee 2019-08-23 16:18 评论0 收藏0
LeetCode 3——无重复字符的最长子串

摘要：题目解答方法一我们从前往后遍历字符串，代表最长子串的起始位置，一开始设置为零。如果没有遇到重复字符，则更新子串的长度，向后遍历。最长子串的起始位置重复的字符在子串中的位置初始化映射自动初始化为零获取更多精彩，请关注 1. 题目 showImg(https://segmentfault.com/img/remote/1460000016867082); 2. 解答 2.1. 方法一我们...

Rocture 2019-07-31 11:16 评论0 收藏0