52XUE Logo

好好学习,天天向上



LeetCode刷题(3):无重复字符的最长子串


示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。


题解:

       假设字符串长度是n,我们循环n次,每次都判断是否有重复字符串,由于判断重复字符串也要循环n次(这里php有个内置函数strpos可以用,但我们做算法题尽量不依赖独有的内置函数),那么时间复杂度是O(n^2),显然这也不可行。思来想去没有特别清晰的思路,查看大神们的解法有一种叫“滑动窗口”,研究了一下终于解出来了。

如下:

class Solution3 {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring1($s) {
        $count = strlen($s);
        $maps = [];
        $max = $len = $start = 0;
        for($end=0;$end<$count;$end++){
            $str = $s[$end];
            // 如果有重复字符,或者再次重复,重置长度重新计数
            if(isset($maps[$str]) && $maps[$str] >= $start){
                $start = $maps[$str];
                $len = $end - $start; 
            }else{
                $len++;
            }

            // 如果最新计数的长度超过当前长度
            $max = $max < $len ? $len : $max;
            $maps[$str] = $end;
        }

        return $max;
    }
}

执行用时 :12 ms, 在所有 php 提交中击败了97.17%的用户

内存消耗 :14.9 MB, 在所有 php 提交中击败了48.77%的用户

        

        滑动窗口到底是什么呢?其实就是在本题中,就是记录起始指针start,和结束指针end,如果他们的长度len超过了目前窗口max的长度,则更新最大值max。本体的关键就是何时更新start。前面讲到,

        如果循环去判断字符串是否有重复字符会导致时间复杂度过高,所以我们将已经处理过的字符都存入hash表,key是字符,value是字符对应的脚标,如果字符存在hash表中,我们就更新下脚标,便于计算最新的len。这里我们会发现测试字符“faaf”输出的结果是3,而答案应该是2。这里最难理解的是   $maps[$str] >= $start  这个条件的判断,$maps[$str]就是当前字符在hash表中的脚标,如果小于等于start,说明它已经判断过,不在当前窗口了,我们丢弃掉不做判断。



作者  :  超人会飞吗

天上地久有时尽,此恨绵绵无绝期。




about me

剪一束月光

秋风清,秋月明。
落叶聚还散,
寒鸦栖复惊。
相思相见知何日,
此时此夜难为情。

联系站长

热门标签