微信创建网站应用程序,wordpress 系列教程,山东泰山队深圳队,七牛云怎么样我生来就是高山而非溪流#xff0c;我欲于群峰之巅俯视平庸的沟壑 1. 题目描述 2. 题目分析与解析
2.1 思路一——暴力解法
看到这个题目#xff0c;我们是不是发现和上一篇内容刚刚讲过的长度最小的子数组题目很像#xff1f;首先自然的暴力解法#xff0c;就是遍历字符…我生来就是高山而非溪流我欲于群峰之巅俯视平庸的沟壑 1. 题目描述 2. 题目分析与解析
2.1 思路一——暴力解法
看到这个题目我们是不是发现和上一篇内容刚刚讲过的长度最小的子数组题目很像首先自然的暴力解法就是遍历字符串的每一个字符从当前位置开始前向后尝试找到最长的不含有重复字符的长度最后得到的所有起始点长度中最大的就是题目的解。
思路 使用两层for循环外层for从字符串每个起点开始 内层for循环不断向后移动找到起点到目前位置的最长不含重复字符串
2.2 思路二——滑动窗口
和上一篇文章讲的一样我们是不是也可以利用滑动窗口的性质减少在窗口内部的内容的对比从而提升时间复杂度根据滑动窗口的思想我们首先定义两个指针表示窗口的头和尾部。从头开始遍历字符串的第一个字符尾部指针从第二个字符开始只要发现当前字符和窗口内的字符都不相等就将尾部指针向后移动。当发现尾部指针开始指向和窗口内某一个字符相同时头部指针就向后移动直到剔除窗口中原有的那个相同的字符。然后继续重复上述过程。
思路 一层for循环尾部指针当发现当前字符和窗口内字符都不相同就把其加入窗口 当发现字符相同记录不相同字符串长度从头部不断移除字符直到串口内部的字符串又不相同 继续移动尾部指针扩充窗口
3. 代码实现
3.1 暴力求解 3.2 滑动窗口 当然代码还能继续优化就是将s.substring(head, end).contains(s.substring(end, end 1))使用hash来判断因为字符串判断子串是很耗时的。改动后如下 4. 相关复杂度分析
4.1 暴力求解 时间复杂度O(n^2)其中 n 是字符串的长度。需要遍历每个下标作为子串的开始下标对于每个开始下标需要遍历其后面的下标得到长度最大的不包含重复字符的字符串。 空间复杂度O(1)。
4.2 滑动窗口 时间复杂度O(n)其中 n 是字符串的长度。指针 head和end 最多各移动 n 次。 空间复杂度O(1)。
