javascript初探LeetCode之3.Longest Substring Without Repeating Characters

题目

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，就是求一字符串的连续子串长度，该子串中不存在重复字符。我的思路是先把字符串转成数组，同时用一个临时数组存放子串。在遍历数组时，如果当前元素在临时数组中已经存在，记录此时子串的最大长度，再把已经存在的元素及之前的元素移出数组，最后把当前元素push到临时数组中，直至遍历完成。

js实现

/**
 * @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){//当前元素已存在
            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;
};

总结

讨论区有个大神用c写的代码执行时间仅为4ms，而上面的js代码执行时间为185ms，他是用指针记录子串的开始和结束，然后对上面代码进行改进，如下：

/**
 * @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){//当前元素已存在
            longest = end -start +1 > longest ? end -start +1 : longest;
            start = index_of + 1;
        }   
        end++;
    });
    return end -start +1 > longest ? end -start +1 : longest;
};

运行时间182ms，好像优化不明显，有兴趣的可以试试再优化一下~