本文介绍: 该题我们可以采用滑动窗口的方法来解决,对于子数组,字串的题都经常用到滑动窗口的解决方法 题目的要求是:1.要获得最长子串的长度 2.子串中不含有重复字符 我们首先看到题目后可以想到的暴力解法就是,去获取字符串中所有的子串,筛选出不含有重复字符的字串,获取其中最长子串的长度,而滑动窗口方法就是在这基础上进行优化 我们以题目给出的示例 1 来进行说明,输入: s = “abcabcbb“,一般遇到输入为字符串的题,通常都需要把字符串转换为字符数组,
代码:
题解:
该题我们可以采用滑动窗口的方法来解决,对于子数组,字串的题都经常用到滑动窗口的解决方法
题目的要求是:1.要获得最长子串的长度 2.子串中不含有重复字符
我们首先看到题目后可以想到的暴力解法就是,去获取字符串中所有的子串,筛选出不含有重复字符的字串,获取其中最长子串的长度,而滑动窗口方法就是在这基础上进行优化
我们以题目给出的示例 1 来进行说明,输入: s = “abcabcbb“,一般遇到输入为字符串的题,通常都需要把字符串转换为字符数组,方便操作
1.我们用 L 指针和 R 指针来遍历字符串,获取字符串的子串(L 和 R 指针之间的字符便是我们当前要讨论的子串),让 L 指针和 R 指针指向 0 下标,此时我们要讨论的子串就是 a,a 里面没有重复的字符,所以我们可以记录该子串的长度,问题来了,我们如何判断当前子串有没有重复的字符呢?我们可以定义一个数组 ascll ,ascll 数组的下标代表字符的 ASCLL 码,数组中的值就代表 ASCLL 码对应的字符在子串中的个数,所以当 R 指针指向 a 时,就将 ascll 数组中,a字符的个数加1,拼接到子串中的字符就是 R 指针指向的字符,即使出现重复,也只会是刚刚拼接的字符重复,所以我们只需要判断刚刚拼接的字符的个数是否大于1,就知道当前讨论的子串中是否出现重复字符,此时 a 字符在 ascll 数组中记录的个数为1,所以该子串不含有重复字符
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。