【LeetCode】无重复字符的最长子串题解
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
复制代码
思路分析
今天的算法题目是字符串处理题目，题目要求 找出其中不含有重复字符的 最长连续子字符串 的长度。
首先，不含有重复字符，我们一般可以使用 hashSet 数据结构来进行排重。普通解法的思路是，对字符串进行双重遍历，分别枚举子字符串，然后满足题目要求，计算答案。
在使用普通解法求解题目的时候，发现在遍历的过程中对子字符串有重复计算法的部分。根据重复计算，我们可以进行优化，采用滑动窗口的思想，动态更新不重复的子字符串。我们两个指针变量，分别指向滑动窗口的左右区间。首先固定左区间位置，然后使用 hashset 判断是否包含重复的字符，更新右区间的位置。遇到重复字符，就更新左区间的位置。具体实现代码如下，供参考。
通过代码
复制代码
总结
普通算法的时间复杂度是 O(n * n)，空间复杂度是 O(n)。
滑动窗口解法的时间复杂度是 O(n)，空间复杂度是 O(1)。
坚持算法每日一题，加油！
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/96ddad281dc0bde63562d2604】。文章转载请联系作者。
数据结构和算法爱好者 2019-09-29 加入
LeetCode,略懂后端的RD
评论