[数据结构与算法]leetcode之无重复字符的最长子串(三)

题目内容

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

 

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:

输入: s = ""
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

暴力(O(n^3))

最简单的，前2层for循环寻找字符串的子串，最后一个for判断这个字串是否无重复

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_num = 0
        for i in range(len(s)):
            for j in range(i, len(s)):
                # 判断者之间有没有重复字符
                dict = {}
                is_ok = True
                for k in range(i, j + 1):
                    if dict.get(s[k]):
                        is_ok = False
                        break
                    dict[s[k]] = 1
                now_str = s[i:j + 1]
                if is_ok and len(now_str) > max_num:
                    max_num = len(now_str)
        return max_num

滑动窗口(O(n^2))

既然是找最大，就不需要重复查找，前面解法中的前两个for循环可以省掉j再次回头，比如已经找到了无重复子串大小为3，那么下次就不需要从头再找，直接在j=i+3的地方查找。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_num = 0
        i = 0
        j = 0
        while j < len(s):
            # 判断者之间有没有重复字符
            dict = {}
            is_ok = True
            for k in range(i, j + 1):
                if dict.get(s[k]):
                    is_ok = False
                    break
                dict[s[k]] = 1
            if is_ok:
                max_num = j + 1 - i
                j += 1
            else:
                i += 1
                j += 1

        return max_num