LeetCode-PHP题解-3-无重复字符的最长子串

文章目录[隐藏]

题目链接
知识点
解法

题目链接

3. longest-substring-without-repeating-characters 难度：medium

知识点

1.滑动窗口法

经典算法，此处不开展

解法

1.暴力循环

此处不赘述

2.滑动窗口

用一个数组做滑动窗口，每次right向右挪动时候，判断该字符串是否在窗口内存在，若不存在则持续右移，记录以后窗口长度；若存在则将左边界置为窗口中该字符的左边。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
     function lengthOfLongestSubstring($s) {
        $len = strlen($s);
        $left = $right = 0;
        $ans = 0;
        $queue = [];
        while($right < $len){
            //判断是否在
            $index = array_search($s[$right], $queue);
            $queue[] = $s[$right];
            if(false !== $index ){
                $queue = array_slice($queue, $index + 1);
            }
            $ans = max($ans, count($queue));
            $right++;
        }
        return $ans;
    }
}

3.滑动窗口2

相比于解法2，这里其实没有应用数组，而是哈希记录了左右边界，每次right向右挪动时候，判断该字符串哈希表里对应的值(str索引)是否在left的左边，若在左边，则left=该索引+1，若不存在则持续右移，记录以后窗口长度；若存在则将左边界置为窗口中该字符的左边。

复杂度剖析

工夫复杂度：O(n)，其中 n 为字符的长度。咱们要遍历字符全副地位，而解决每个地位，包含哈希查找只须要 O(1)的工夫。

空间复杂度：O(n)，最大哈希长度。

以下为PHP语言实现~~~~

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $len = strlen($s);
        $left = $right = 0;
        $ans = 0;
        $queue = [];
        while($right < $len){
            //判断是否在
            $index = array_search($s[$right], $queue);
            if(false !== $index){
                $queue = array_slice($queue, $index);
            }else{
                $queue[] = $s[$right];
                var_dump($queue);
                $ans = max($ans, count($queue));
            }
            $right++;
        }
        return $ans;
    }
}

搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]‍，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：LeetCode-PHP题解-3-无重复字符的最长子串