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

码农天地 -
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;
    }
}
特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系(cy198701067573@163.com),我们将及时处理。

php介绍

PHP即“超文本预处理器”,是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言,与C语言类似,是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习,使用广泛,主要适用于Web开发领域。

Tags 标签

phpleetcodehash

扩展阅读

加个好友,技术交流

1628738909466805.jpg