阅读 207

算法题--寻找最长子串

问题:

有一个长度随机的字符串,寻找它的最长子串。

例子:

输入:

abcabcbb
复制代码

输出:

3
复制代码

思路:

遍历肯定是要遍历,使用两个指针,第一个指向子串首,第二个指向子串尾,当将子串尾向前推进发现和已有子串有重复元素时,改变子串首指针指向当前这个重复元素的后面一位,子串尾的指针一直默认++。

代码如下:

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var length = s.length;
    if (length <= 1) {
        return length;
    }
    var p = 0;  // 首指针
    var q = 1; // 尾指针
    var result = 1;
    while (q < length) {
        var sub = s.slice(p, q); // 获得子串
        var i = sub.indexOf(s[q]); // 子串尾部的下一位的index
        if (i !== -1) {
            p = p + i + 1;  // 子串首部指针指向重复元素i的下一位
        }
        q++;  // 尾部指针一直默认向后推进
        result = q - p > result ? q - p : result;  // 每一次判断都和上一次的结果对比
    }
    return result;
};
复制代码
关注下面的标签,发现更多相似文章
评论