题目
leetCode地址：
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"输出: 3 解释: 无重复字符的最长子串是 "abc"，其长度为 3。复制代码
示例 2:
输入: "bbbbb"输出: 1解释: 无重复字符的最长子串是 "b"，其长度为 1。复制代码
示例 3:
输入: "pwwkew"输出: 3解释: 无重复字符的最长子串是 "wke"，其长度为 3。请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。复制代码
解答
class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ stringMap ={} longestLength,start =0,0 for index,char in enumerate(s): start = max(start,stringMap.get(char,-1) +1) longestLength = max(longestLength,index-start+1) stringMap[char]=index return longestLength复制代码 该题主要考察了hashMap数据结构 的应用
变量含义
- stringMap：字符
char作为键，字符在字符串中最新出现的下标index作为值 - longestLength：子串最长长度，初始为0
- start：当前子串开始的下标，初始为0
代码解析
-
start = max(start,stringMap.get(char,-1) +1)：确定子字符串开始的位置。首先，判断该字符在map中是否出现过，出现过的话，再进一步判断该字符是否在在当前子字符串中（通过判断其下标是否比start大）如果比start大，，代表当前的char在当前子字符串中出现过，这时需要 将子字符串中出现该char的下标+1,并把该下标设为新子字符串开始的下标start，以保持子字符串中不会出现重复字符；如果没有出现过，start保持不变 -
longestLength = max(longestLength,index-start+1):接下来判断当前的子字符串最长长度longestLength`是否有变化。什么情况才会有变化呢？当前子字符串的长度大于之前记录的最长程度时。 -
stringMap[char]=index: 最后更新当前字符char最新出现的下标index。这一步非常关键，只有及时更新其下标，才能确保该字符的下标是字符串中最新出现的下标