題目

Given a string, find the length of the longest substring without repeating characters.

example

Given"abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke"is a subsequence and not a substring.

分析

這是leetcode上的第3題，難度為medium，就是求一字符串的連續(xù)子串長(zhǎng)度，該子串中不存在重復(fù)字符。我的思路是先把字符串轉(zhuǎn)成數(shù)組，同時(shí)用一個(gè)臨時(shí)數(shù)組存放子串。在遍歷數(shù)組時(shí)，如果當(dāng)前元素在臨時(shí)數(shù)組中已經(jīng)存在，記錄此時(shí)子串的最大長(zhǎng)度，再把已經(jīng)存在的元素及之前的元素移出數(shù)組，最后把當(dāng)前元素push到臨時(shí)數(shù)組中，直至遍歷完成。

js實(shí)現(xiàn)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var arr = s.split('');
    var longest = 0;
    var temp = [];
    arr.forEach(function(value){
        let index_of = temp.indexOf(value);
        if(index_of!=-1){//當(dāng)前元素已存在
            longest = temp.length > longest ? temp.length : longest;
            for(let i = 0;i <= index_of;i++){
                temp.shift();
            }
        }
        temp.push(value);
    });
    return temp.length > longest ? temp.length : longest;
};

總結(jié)

討論區(qū)有個(gè)大神用c寫的代碼執(zhí)行時(shí)間僅為4ms，而上面的js代碼執(zhí)行時(shí)間為185ms，他是用指針記錄子串的開始和結(jié)束，然后對(duì)上面代碼進(jìn)行改進(jìn)，如下：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var arr = s.split('');
    var longest = 0;
    var start = 0,end = -1;
    arr.forEach(function(value){
        let index_of = arr.indexOf(value,start);//不能從頭開始遍歷
        if(index_of >= start && index_of <= end){//當(dāng)前元素已存在
            longest = end -start +1 > longest ? end -start +1 : longest;
            start = index_of + 1;
        }   
        end++;
    });
    return end -start +1 > longest ? end -start +1 : longest;
};

運(yùn)行時(shí)間182ms，好像優(yōu)化不明顯，有興趣的可以試試再優(yōu)化一下~