Leetcode No.3 无重复字符的最长子串

小灰灰 2022-05-17 04:46 24阅读 0赞

# 问题描述： #

给定一个字符串，找出不含有重复字符的**最长子串**的长度。

## **示例：** ##

给定 `"abcabcbb"` ，没有重复字符的最长子串是 `"abc"` ，那么长度就是3。

给定 `"bbbbb"` ，最长的子串就是 `"b"` ，长度是1。

给定 `"pwwkew"` ，最长子串是 `"wke"` ，长度是3。请注意答案必须是一个**子串**，`"pwke"` 是 *子序列  *而不是子串。

# 思路与分析： #

## 1.brute-force的暴力方法： ##

### 思路： ###

枚举字符串的所有子串，判断每一个子串是否含有重复字符，若不含，计算当前的最优解ans = max(ans, len(s'))

### 复杂度： ###

判断是否含有重复字符需要用O(n)时间遍历子串；

生成子串 s(i,j) 的个数：每固定一个i，对应的 j 取值在 i+1 ~ j 之间， 子串总数为O(n^2)

故复杂度为O(n^3)

用这种算法实现的code在提交后会提示Timeout，必须进行优化

## 2.滑窗法+Hash Table ##

### 思路： ###

用字典来存储子串的元素：newset = \{\}

分别用i, j作为左右边界，拿来框住字符串从i到j那一段，想象这样的一个滑动的窗口，随着i、j的移动而滑动；我们就这样用 \[ i, j ) 来表示字符串s的子串s(i , j)，不必枚举所有子串，只需判断当前元素是否包含在滑窗中。

初始时i = j = 0，顺序扫描字符串s，判断当前元素 s\[ j \] 是否包含在字典中：若包含，则 i ++， 相当于缩小滑窗，直到当前元素不再出现在滑窗中，同时删除字典中key为 s\[ i \] 的元素；若不含，则 j ++，相当于当前元素加入滑窗中，同时将它加入字典。

同样的，每次纳入新元素时，求当前最优解 ans = max(ans, j - i)。

注意：为什么要使用字典？这是为了提高这一步的效率：判断当前元素是否包含在子串中

用列表或者字符串来存储元素时，每次查询操作都要O(n)的时间，这就造成了低效；Python的字典实质上是哈希表 ( Hash Table )，查询操作只需O(1)时间，这样就能优化算法了。

### 复杂度： ###

遍历字符串需要O(n)时间，遍历每个字符时的查询操作需要O(1)时间；

故复杂度为O(n)。

# 代码实现（Python）: #

class Solution(object):  
    def lengthOfLongestSubstring(self, s):  
        """  
        :type s: str  
        :rtype: int  
        """  
        n = len(s)  
        i, j, ans = 0, 0, 0  
        newset = \{\}  
        while j < n:  
            if s\[j\] not in newset:  
                newset\[s\[j\]\] = 0  
                j += 1  
                ans = max(ans, j-i)  
            else:  
                del newset\[s\[i\]\]  
                i += 1  
        return ans