LeetCode(PHP)之无重复字符的最长子串

题目：无重复字符的最长子串(Longest Substring Without Repeating Characters)

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

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

示例 2:

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

示例 3:

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

思路：

• 这道题采用暴力解法时间复杂度会很高会达到 ，故采取滑动窗口的方法降低时间复杂度。
• 什么是滑动窗口？
  滑动窗口是双指针的应用，一个指针指向开始位置，另一个指向结束位置，两指针中间位置即为窗口，通过移动两个指针的位置来控制窗口的大小（双指针确定一个窗口）。
• 如何移动指针来得到答案？
  我们可以把窗口看作一个队列，每次往队列中添加一个字符，如果存在相同的则把队列左边元素移除，直到满足题目要求！

暴力法：

这里是转换成数组来处理的。

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
         // 字符串长度
        $length = strlen($s);
        // 字符串转为数组
        $arr = str_split($s);
        // 最长子串的长度
        $ans = 0;
        for($i = 0; $i < $length; $i++){
            // 用于存储不重复的字符
            $checkedArr = [];
            for($j = $i; $j < $length; $j++){
                // 判断当前字符是否已经存在于数组中，存在就跳出当前循环，不存在就将字符加入数组中并更新 最长子串的长度
                if(!in_array($arr[$j], $checkedArr)){
                    array_push($checkedArr, $arr[$j]);
                    if(count($checkedArr) > $ans){
                        $ans = count($checkedArr);
                    }
                }else{
                    break;
                }
            }
        }
        return $ans;
   ｝
}

滑动窗口：

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        // 字符串长度
        $length = strlen($s);
        // 存放最长子串
        $arr = array();
        $ans = $i =  $j =0;
        // i为左侧指针,j右侧指针
        while($i < $length && $j < $length){
            // 判断右侧指针指向的值是否存在
            if(!in_array($s[$j], $arr)){
                // 如果不存在将j指向的值入队
                array_push($arr, $s[$j++]);
                // 更新最长子串长度 j - i 为当前滑动窗口的长度
                $ans = max($ans, $j - $i);
            }else{
                // 如果存在相同值, 则出队
                array_shift($arr);
                // 并更新左侧指针的位置
                $i++;
            }
        }
        return $ans;
    }
}

优化滑动窗口：

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        $length = strlen($s);
        $ans = 0;
        // 用于存储子串(不会有重复的字符)
        $str = '';
        for($i = 0; $i < $length; $i++) {
            // 判断有无重复,返回第一次出现的位置或false
            $index = strpos($str, $s[$i]);
            if($index !== false){
                // 有重复，从重复位置开始截取后面的内容
                $str = substr($str, $index + 1);
            }
            $str .= $s[$i];
            $ans = max(strlen($str), $ans);
        }
        return $ans;
    }
}