问题
给定一个字符串,找出其中不含有重复字符的最长子串长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
暴力求解
枚举所有字符子串,获取长度最长的无重复字符子串。
分析程序,匹配在给定字符串中是否有重复字符isRepeating函数的时间复杂度是O(n)。因此,完成算法的时间复杂度是O(n³);空间复杂度是O(min(n, m)),其中n是字符串的长度,m是相异字符的数量。
从算法分析,如果从 0 到 j-1 是无重复字符子串,第j项元素同前面的任意一个元素重复,则不管第j项后面有无元素,0滑动窗口求解
1)如果从 0 到 j-1 是无重复字符子串,第j项元素同前面的任意一个元素重复,则不管第j项后面有无元素,0
2)移动开始索引位置,直到没有重复元素为止,此时为没有重复元素的子串,第j项作为结束索引继续向后移动,直到待判断的字符串结束为止,判断是否出现重复。如果出现重复,则继续重复2)。
滑动窗口算法优化了暴力求解法,当结束索引到第j项出现重复,不再向后继续判断,而是移动开始索引,直到没有重复元素为止,再继续向后移动结束索引,避免冗余判断。
在最坏情况下,字符串所有元素都会被开始索引和结束索引各遍历一次。时间复杂度是O(2n)=O(n)。空间复杂度是O(min(n, m)),其中n是字符串的长度,m是相异字符的数量。
分析算法发现,当出现一次重复时,我们移动开始索引位置,直到剔除重复元素为止。如果在移动过程中,未剔除重复元素,则一直要移动开始索引。因此,我们可以考虑让开始索引移动位置一步到位。
优化滑动窗口求解
优化滑动窗口求解方法,当出现判断字符为重复项时,直接将窗口的开始索引位置置于重复项的下一个元素继续判断。
时间复杂度是O(n)。空间复杂度是O(min(n, m)),其中n是字符串的长度,m是相异字符的数量。
性能分析
随机5000个字符的待匹配字符串进行测试:
The length of longest substring is 42 by Violence solve, using time is 2908 milliseconds.
The length of longest substring is 42 by Sliding Window solve, using time is 2 milliseconds.
The length of longest substring is 42 by Optimizing Sliding Window solve, using time is 2 milliseconds.
通过测试结果分析,移动窗口算法性能优异,时间复杂度是线性增长。
领取专属 10元无门槛券
私享最新 技术干货