leetcode3-最长无重复子串

原题链接： 题目描述：在字符串s中计算最长无重复的子串 思路一：采用双指针的方法处理，开始和结束指针，结束指针从头往后遍历一遍，遍历的过程中当前这个元素如果在这个子串中，开始指针重新计算（开始指针加上移动的元素个数），没有在这个子串中，重新计算长度，遍历完成后返回长度。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
          
   
    let len = s.length
    let res = 0
    for (let start = 0, end = 0; end < len; end++) {
          
   
        let index = s.slice(start, end).indexOf(s[end])
        if (index !== -1) {
          
   
        	//index是下标，从0开始的，移动的元素个数为index+1
            start = start + index + 1
        }
        res = Math.max(res, end - start + 1)
    }
    return res
};

思路二：利用数组来存储

let s = abbbc
function longestSubstring(s) {
          
   
    let res = [], max = 0
    for (let i = 0; i < s.length; i++) {
          
   
        let index = res.indexOf(s[i])
        //找到值进行截取
        if (index != -1) {
          
   
            res.splice(0, index + 1)
        }
        res.push(s[i])
        //没找到重新计算长度
        max = Math.max(max, res.length)
    }
    return max
}
console.log(longestSubstring(s))

思路三：利用map查找当前元素是否已经存在，如果存在重新计算开始位置，不存在重新计算长度

var lengthOfLongestSubstring = function(s) {
          
   
    let map = new Map()
    let left = 0, res = 0
    for (let i = 0; i < s.length; i++) {
          
   
        //如果map中存在当前字符，重新计算左侧开始位置的指针
        if (map.has(s[i])) {
          
   
            left = Math.max(map.get(s[i]) + 1, left)
        }
        res = Math.max(res, i - left + 1)
        //key值相同的时候，后面会覆盖前面的
        map.set(s[i], i)
    }
    return res
};