3. 无重复字符的最长子串(lengthOfLongestSubstring)
时间：07-04来源：作者：点击数：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：leetcode 国内网/problems/longest-substring-without-repeating-characters
题解1：
执行用时：184 ms, 在所有 PHP 提交中击败了18.20% 的用户
内存消耗：19.5 MB, 在所有 PHP 提交中击败了19.21% 的用户
通过测试用例：987 / 987
查看代码
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$len = strlen($s);
if(0 == $len)
return 0;
$list = [];
for($i=0;$i<$len;$i++){
$temp = $s[$i];
$list[$i] = 1;
for($j=$i+1;$j<$len;$j++){
if(false === strpos($temp, $s[$j])){
$list[$i] += 1;
$temp .= $s[$j];
}else
break;
}
}
return max($list);
}
}题解2：
执行用时：20 ms, 在所有 PHP 提交中击败了59.83% 的用户
内存消耗：18.8 MB, 在所有 PHP 提交中击败了46.29% 的用户
通过测试用例：987 / 987
查看代码
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$len = strlen($s);
$max = 0;
$tempStr = '';
for($i=0;$i<$len;$i++){
if(0 == $i){
$max = 1;
$tempStr = $s[$i];
continue;
}
$index = strpos($tempStr, $s[$i]);
if(false === $index){
$tempStr .= $s[$i];
}else{
$max = max($max, strlen($tempStr));
$tempStr = substr($tempStr, $index + 1) . $s[$i];
}
}
return max($max, strlen($tempStr));
}
}题解3：
执行用时：16 ms, 在所有 PHP 提交中击败了75.84% 的用户
内存消耗：19.6 MB, 在所有 PHP 提交中击败了18.48% 的用户
通过测试用例：987 / 987
查看代码
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$len = strlen($s);
$list = [];
$tempStr = '';
for($i=0;$i<$len;$i++){
if(0 == $i){
$tempStr = $s[$i];
continue;
}
$index = strpos($tempStr, $s[$i]);
if(false === $index){
$tempStr .= $s[$i];
}else{
$list[] = strlen($tempStr);
$tempStr = substr($tempStr, $index + 1) . $s[$i];
}
}
$list[] = strlen($tempStr);
return max($list);
}
}更新：
题解4：
执行用时：4 ms, 在所有 PHP 提交中击败了99.7% 的用户
内存消耗：19.9 MB, 在所有 PHP 提交中击败了16.6% 的用户
通过测试用例：987 / 987
解题思路：把不重复子串转变为求连续整数的个数。
查看代码
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$list = [0];
$order = [];
$len = 0;
$begin = 1;
for($i=0;$i<strlen($s);$i++){
$str = $s[$i];
$index = $i + 1;
if(empty($order[$str]) || $order[$str] < $begin){
$len++;
$order[$str] = $index;
}else{
$list[] = $len;
$begin = $order[$str] + 1;
$len = $index - $order[$str];
$order[$str] = $index;
}
}
$list[] = $len;
return max($list);
}
}方便获取更多学习、工作、生活信息请关注本站微信公众号
湘公网安备 43102202000103号