Leetcode 编程训练[3]:Longest Substring Without Repeating Characters

2015-03-25

2 min read

#3：题目为求出最长没有重复字符的字符串，输出最大长度。还是比较容易的，主要是注意JS的字符串操作就行了。

比如字符串的属性.length表示该字符串的长度，方法.charAt(index)表示取出一个字符串中指定位置index的字符，indexOf(char)用来寻找指定字符char第一次出现的位置位置，以及substr(beginIndex, subLength)截取子字符串（注意第二个参数是子字符串的长度）。

第一次成功通过的代码，如下。耗时320ms。具体问题见注释。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var length = 0;
    var result = 0;
    var str = '';
    //映射表对象存储 key == str , value == length
    var map = {};//映射表适合在调试时使用，最后发现map可以不用，而改用一个maxLen来记录最大长度。
    for(var i = 0; i < s.length; i++){
        str += s.charAt(i);
        length ++;
        if(str.indexOf(s.charAt(i)) != (length - 1)){
        	//在判断有重复字符串后，截取重复字符第一次出现位置之后的字符为新备选最大字符串。
            str = str.substr(str.indexOf(s.charAt(i)) + 1, length - str.indexOf(s.charAt(i)));
            length = str.length;
        }else{
            map[str] = length;
        }
    }
	//对象的历遍耗时太大，可以使用标记位
    for(str in map){ 
        if(str.length > result){
            result = str.length;
        }
    }
    return result;
};

经过修改，速度得到来提升。加快来100ms的样子。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var len = 0;
    var maxLen = 0;
    var str = '';
    for(var i = 0; i < s.length; i++){
        str += s.charAt(i);
        len ++;
        if(str.indexOf(s.charAt(i)) != (len - 1)){
            str = str.substr(str.indexOf(s.charAt(i)) + 1, len - str.indexOf(s.charAt(i)));
            len = str.length;
        }
            maxLen = maxLen > len ? maxLen: len;
    }
    return maxLen;
};

这次离JS第一梯队没有太远，可见这道题目还是蛮容易的。

源码

Leetcode 编程训练[3]:Longest Substring Without Repeating Characters

See Also