3. 無重復字符的最長子串

lily_wang 發(fā)布于2019-08-23 14:17 / 1087人閱讀

摘要：題目給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。

題目：給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。

示例 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循環(huán)操作，這樣暴力寫我們的leetcode肯定是不會給過的，因為遇到超級長的字符串測試用例，執(zhí)行時間會超出時間限制，上面代碼的優(yōu)化空間很大。
理一下邏輯，我們每次在2里面檢測出有重復的字符時，記錄這個重復字符前一次出現(xiàn)的位置index，然后中斷這次循環(huán)，開始下一次1的循環(huán)，并且i的位置應該為index+1。

比如在i=0的時，在2循環(huán)里j=4時就會出現(xiàn)重復的字符d，字符d前一次出現(xiàn)的位置是1，這時最長字符串長度是4，并且被記錄，這時應該開始1循環(huán)的下一次循環(huán)，并且是從i=2開始。
3循環(huán)和2循環(huán)其實是不必要的，我們創(chuàng)建一個動態(tài)的字符串，把每次循環(huán)到的字符加進去并實時記錄它的長度，遇到重復的字符串就砍掉字符第一次出現(xiàn)跟它之前的字符串，比如上圖，i循環(huán)到4時，出現(xiàn)重復字符d,d在之前出現(xiàn)的位置是1，我們應該砍掉動態(tài)字符串位置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語言

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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. 無重復字符的最長子串

摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。完成循環(huán)后取隊列中出現(xiàn)的最大長度即可。給定一個字符串，請你找出其中不含有重復字符的?最長子串?的長度。示例?1：輸入: abcabcbb 輸出: 3 解釋: 因為無重復字符的最長子串是 abc，所以其長度為 3。示例 2：輸入: bbbbb 輸出: 1 解釋:...

qc1iu 2019-08-23 18:32 評論0 收藏0
LeetCode.3 無重復字符的最長子串(JS)

摘要：先跳到第三題是因為第二題第一眼沒讀懂一題目無重復字符的最長子串給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。以此來實現(xiàn)判斷是否包含重復字符。先跳到第三題是因為第二題第一眼沒讀懂一、題目無重復字符的最長子串：給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例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