【打卡贴】（No.003）从零开始刷LeetCode

击上方“Ahab杂货铺”，选择“置顶公众号”

技术分享第一时间送达！

---

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

原题：

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

示例 1:

输入: "abcabcbb"输出: 3 解释: 无重复字符的最长子串是 "abc"，
    其长度为 3。

示例 2:

输入: "bbbbb"输出: 1
解释: 无重复字符的最长子串是 "b"，
    其长度为 1。

示例 3:

输入: "pwwkew"输出: 3
解释: 无重复字符的最长子串是 "wke"，
    其长度为 3。      请注意，答案必须是一个子串，
    "pwke" 是一个子序列 而不是子串。

---

昨天上课老师刚好在讲字符串，没有听课偷偷把这个题给刷了，快下课的时候已经在写第二种方法了，废话不说直接上解析。

解析：

首先想到就是简单粗暴的逐个检查所有的子字符串，看它是否不含有重复的字符。不用想执行效率很低。

ef Substring(s):
if s == '':
return 0
   if len(s) == 1:
return 1
   record = 0
   for i, char in enumerate(s):
li1 = set()
for st in s[i:]:
if st not in li1:
li1.add(st)
if len(li1) > record:
record = len(li1)
else:
break
   return record

第二种方法解题思路：

借助一个辅助键值对来存储某个元素最后一次出现的下标。用一个整形变量存储当前无重复字符的子串开始的下标。

def Substring(s):
max_len = 0
# 判断传入的字符串是否为空
  if s is None or len(s) == 0:
return max_len
# 定义一个字典，
#存储不重复的字符和字符所在的下标
  str_dict = {}
# 存储每次循环中最长的子串长度
  one_max = 0
# 记录最近重复字符所在的位置+1
  start = 0
  for i in range(len(s)):
# 判断当前字符是否在字典中和当前字符的下标
#是否大于等于最近重复字符的所在位置
   if s[i] in str_dict and str_dict[s[i]] >= start:
# 记录当前字符的值+1
       start = str_dict[s[i]] + 1
# 在此次循环中，最大的不重复子串的长度
   one_max = i - start + 1
# 把当前位置覆盖字典中的位置
   str_dict[s[i]] = i
# 比较此次循环的最大不重复子串长度
#和历史循环最大不重复子串长度
   max_len = max(max_len, one_max)
return max_len

---

中秋假期的第一天释放了自己的天性在床上瘫了一天，所以更新比较晚，今天的文章开赞赏了，嘻嘻，希望明天午饭加个鸡腿。