让我们一起啃算法----无重复字符的最长子串

无重复字符的最长子串

这是 LeetCode 第三题，题干如下：

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
  输入: “abcabcbb”
  输出: 3
  解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
  输入: “bbbbb”
  输出: 1
  解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
  输入: “pwwkew”
  输出: 3
  解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。
来源：力扣

解题思路

常规思路：两层循环字符串，并且我们需要一个 Map字典 来标记哪些字符已经出现过，流程如下：

GO语言的代码实现：

func lengthOfLongestSubstring(s string) (length int) {
    if "" == s {
        return
    }
    length = 1
    for i := 0; i < len(s); i++ {
        // 字符的ASCII范围在0-127，所以这里申明了map的key类型为uint8
        dict := make(map[uint8]bool)
        dict[s[i]] = true
        for j := i + 1; j < len(s); j++ {
            // 判断字符是否在map中，如果存在就直接跳出循环
            if _, ok := dict[s[j]]; ok {
                break
            }
            // 将字符放入map中
            dict[s[j]] = true
            // 每次都计算最大值
            cMax := j - i + 1
            if cMax > length {
                length = cMax
            }
        }
    }
    return
}

这个题目，其实主要的考点在于对 滑动窗口 的理解。

滑动窗口：滑动窗口是数组、字符串问题中常用的抽象概念。
窗口通常是在数组、字符串中由开始和结束索引定义的一系列元素的集合，即 [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
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a...

leetcode 算法最长不重复子串滑动窗口

本作品采用《CC 协议》，转载必须注明作者和本文链接

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

5 人点赞

从零开发一个电商项目，功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

讨论数量: 5

lidongyoo

课程读者 304 声望

mark

4年前评论

captain2021

Laravel 5.8 译者 422 声望 / 开发 @ 谈笑风生

厉害

4年前评论

三斤和他的喵（楼主）

一起加油

captain2021 （作者）

@三斤和他的喵大佬这个有php的实现吗？我卡住了，不知道用php怎样实现

三斤和他的喵

课程读者 172 声望

@hxd 抱歉呀，现在才有空，php的代码如下：

function lengthOfLongestSubstring($s) {
    $start = 0;
    $str = "";
    $count = 0;
    for($i = 0; $i < strlen($s); $i++) {
        $index = strpos($str, $s[$i]);
        // 找到了字符
        if ($index !== false) {
            $start += $index + 1;
        }

        $str = substr($s, $start, $i+1-$start);

        if (strlen($str) > $count) {
            $count = strlen($str);
        }
    }
    return $count;
}

4年前评论

captain2021

非常感谢

三斤和他的喵（作者）（楼主）

@hxd 没事，共成长 :wave:

fengchenorz

5 声望

滑动窗口概念好评 :+1:

$length = 1;
for ($i = 0; $i < strlen($str); $i++) {
    $tmpStr = $str[$i];
    for ($j = $i + 1; $j < strlen($str); $j++) {
        if (strpos($tmpStr, $str[$j]) === false) {
            $tmpStr .= $str[$j];
            if (strlen($tmpStr) > $length) {
                $length = strlen($tmpStr);
            }
            continue;
        }
        break;
    }
}

4年前评论

三斤和他的喵（楼主）

:+1:

取名字好烦。

0 声望

mark

4年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

让我们一起啃算法----无重复字符的最长子串

无重复字符的最长子串

解题思路

总结

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

让我们一起啃算法----无重复字符的最长子串

无重复字符的最长子串

解题思路

总结

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录