leetcode 3. 无重复字符的最长子串

第一种:也是我写的,弱智写法,两个for不断循环累积子串判断有没有重复

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (s =='') return 0
    let count = 1,max = 1
    for(let i = 0; i< s.length; i++) {
        let tmp = new Map()
        tmp.set(s[i],1)
        for (let j = i+1; j < s.length; j++) {
            if(!tmp.has(s[j])) {
                tmp.set(s[j],1)
                count ++
            }
            else {
                count = 1
                break
            }
            if(count>max) max = count
            if(j ==  s.length-1) count =1
        }
    }
    return max
};

时间复杂度为O(n^3)

第二种,通过迭代字符串然后slice截取字符串再用indexof找到重复的字符串,遇到重复的就把startnum重置,最后找到最长子串

var lengthOfLongestSubstring = function(s) {
    let startNum = 0;
    let maxNum = 0;
    s.split('').forEach((v, i) => {
        const index = s.slice(startNum, i).indexOf(v);
        if(index === -1) {
            // 无重复字符
            maxNum = Math.max(maxNum, i - startNum + 1);
        } else {
            // 重复字符
            startNum = index + startNum + 1;
        }
    });
    return maxNum;
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注