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

题意

解题思路:

思路

• 定义一个map存储(k, v)，其中k值为字符，v值为字符位置：[abc]；
• 从i = 0开始，不断向后移动，直到map中有重复值[abca]；
• 遇到重复值则把队列的左边的元素移出[bca]，重新更新开始位置start；
• 继续移动i指针，当map中不存在重复值，更新字符串长度；
  

PHP 代码实现

class Solution {
    function lengthOfLongestSubstring($s) {
        $hash = [];
        $start = 0;
        $maxStrLen = 0;
        for ($i = 0; $i < strlen($s); $i++) {
            if (isset($hash[$s[$i]]) && $start <= $hash[$s[$i]]) {
                $start = $hash[$s[$i]] + 1;
            } else {
                $maxStrLen = max($maxStrLen, $i - $start + 1);
            }
            $hash[$s[$i]] = $i;
        }
        return $maxStrLen;
    }
    function lengthOfLongestSubstring($s) {
        $counts = [];
        $i = 0; $j = 0;
        $maxStrlen = 0;
        for (; $i < strlen($s); ++$i) {
            for (; $j < strlen($s); ++$j) {
                if ($counts[$s[$j]] != 0) break;//表示出现过相同值
                $counts[$s[$j]] += 1;
            }
            $maxStrlen = max($maxStrlen, $j - $i);
            $counts[$s[$i]] -= 1;
        }
        return $maxStrlen;
    }
}

GO 代码实现

func lengthOfLongestSubstring(s string) int {
    var strMap = make(map[byte]int)
    start, maxStrLen := 0, 0
    for i := 0; i < len(s); i++ {
        if v, ok := strMap[s[i]]; ok {
            start = max(start, v + 1)
        }
        strMap[s[i]] = i
        maxStrLen = max(maxStrLen, i - start + 1)
    }
    return maxStrLen
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}