原文链接：go leetcode
无重复字符的最长子串
这是 LeetCode 第三题，题干如下：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。 来源：力扣
解题思路
常规思路：两层循环字符串，并且我们需要一个 Map字典 来标记哪些字符已经出现过，流程如下：
这个题目，其实主要的考点在于对滑动窗口的理解。
滑动窗口：滑动窗口是数组、字符串问题中常用的抽象概念。 窗口通常是在数组、字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。 而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j) 向右滑动 1 个元素， 则它将变为 [i+1, j+1)[i+1,j+1)（左闭，右开）。
那么借用滑动窗口的概念，如何来解题呢？我这里画了一张示意图，其中 [X,Y) 就是 滑动窗口：
这里有一个注意点：当 Y 指向的字符在 [X,Y) 滑动窗口之间时，假设索引值为 index，这时候 X 是直接移动到 index+1 的位置。
Go 实现：
func lengthOfLongestSubstring(s string) int {
var Length int
var s1 string
x := 0
y := 0
s1 = s[x:y]
for ; y < len(s); y++ {
// strings.IndexByte 用于判断y对应的字符是否在[x,y)中，不存在返回-1
if index := strings.IndexByte(s1, s[y]); index != -1 {
// 如果存在的话，x直接跳到index的后一位
x += index + 1
}
s1 = s[x : y+1]
if len(s1) > Length {
Length = len(s1)
}
}
return Length
}
PHP 实现：
function lengthOfLongestSubstring($s)
{
$start = 0;
$str = "";
$count = 0;
$length = strlen($s);
$result = '';
for($i = 0; $i < $length; $i++) {
$index = stripos($str, $s[$i]);
// 找到了字符
if ($index !== false) {
$start += $index + 1;
}
$str = substr($s, $start, $i+1-$start);
if (strlen($str) > $count) {
$count = strlen($str);
$result = $str;
}
}
return $result;
}
echo lengthOfLongestSubstring('abcabcbb'); // output: bac
最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券
