题目:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
解题思路
设置子字符串 sub
,初始化为空字符串。
设置游标 point
,指向主字符串(参数)中第 n 个字符串位置,初始化 0
设置子字符串在主字符串中的游标 subPoint
(头对头),初始化 0
增加游标 point
值,以及对应字符,检查其在子字符串中的位置 pos
,如果不存在,则还不构成重复。这种情况,将对应字符追加到 sub
,并且重新统计最大不重复子字符串长度 max
。
但如果 point
对应字符在子字符串中的位置 pos
有值,则要改变 subPoint
来一次重新统计。
最不需要动脑的想法,就是将 subPoint++
,即将子字符串在主字符串上往后挪一格,但为了获得更好的性能,我们是否可以不一点点将 subPoint
往后移动?
答案是可以的,用例子最好说明:
在 ABCDCEFGH
这个字符串中,一开始,子字符串最多可以到 ABCD
,往后遇到第一个重复字符 C
,同时可以发现,C
出现在 ABCD
的第三位。很明显,如果 subPoint
只移动一格,也就是子字符串从 B
开始重新统计,是没有必要的,因为我们已经知道 B
后会有 C
,而且这个 C
会跟第二个的 C
重复,而且这个 C
重复时,子字符串因为少了 A
反而字符长度还没有第一次统计的长度长,完全是浪费操作。
所以我们能不能利用之前已知的某些结果?当然是可以的。我们可以直接将 subPoint
移动到 C
之后开始统计,而 C
之后的位置,就是 subPoint + pos + 1
,这里稍微处理一下,处理速度会获得第一个质的提升。
接下来,如果还是用偷懒的方式,我们只用再重新一个个字符拼凑子字符串,但实际上,重新统计子字符串,依然不用每次都从零开始。
直接用上面的例子说明。通过观察和思考,我们可以得出一个其实还算明显的结论:第一个 C
和第二 C
之间,是不可能出现重复字符串的(因为有的话,最早出现重复的就不是第二个 C
了),所以对于第 2 次子字符串统计来说,初始化子字符串就是从 第一个 C
到第二个 C
之间的字符(包含第二个 C
,虽然包不包含没有太大影响,但毕竟又省去了一次循环)。 PHP 通过 substr
很容易做到。通过这步的处理,执行效率又会上升一个档次。
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLongestSubstring($s) {
$point = 0;
$subPoint = 0;
$len = strlen($s);
$max = 0;
$sub = '';
while ($point < $len) {
$pos = strpos($sub, $s[$point]);
if (false === $pos) {
$sub .= $s[$point];
++$point;
$max = max($max, strlen($sub));
} else {
++$pos;
$subPoint += $pos;
if ($subPoint + $max > $len) {
return $max;
}
$sub = substr($sub, $pos).$s[$point];
$point = $subPoint + strlen($sub);
}
}
return $max;
}
}
这次的执行效率打败了 96.8% 的人,内存占用更是侥幸打败了 100%,对自己相当满意(滑稽)。
看了 LeetCode 的官方解题思路,其中提到了关键词『滑动窗口』,其实就是上面两点结合后更简介的总结,即:如果目前找到的子字符串 s 中有一格字符 c ,已经与紧跟 s 后面的字符相同,则将 s 中字符 c 之前的字符删除(包括 c 本身),再一点点向后比较。是不是感觉有滑动的画面感了?
LeetCode 刷题之无重复字符最长子串 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

写作累,服务器还越来越贵
求分担,祝愿好人一生平安
天使打赏人