LeetCode力扣_第三题_无重复字符的最长子串

第一次写专栏

原因有俩：一是怕忘故作记录，当成笔记来记录；二是激励自己学习。

废话不多说，上题：

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

题目很容易理解，给个例子：

输入: s = "abcabcbb"

输出: 3 

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

答：首先思路是这样的，因为字串内不能有重复的字符，这是个判别条件。最终的目的是返回最长字串的长度。因此需要筛选出字符串内所有的不含重复字符的字串，然后计算长度，再得最大值。

        字串计算长度是首-尾+1，那么这里就是要确定首部和尾部，首部就是遍历的时候位置，而尾部要保证首尾字串中无重复字符。因此在往前遍历的时候，若是出现与后面重复的字符的时候，尾部应该调整到后面重复字符前的一位，再来计算长度。

流程图：

下面是代码实现（python3）：

1class Solution:

2   def lengthOfLongestSubstring(self, s: str) -> int:

3        ans=0 %存储最大字串长度

4        i=0%尾部

5        pd={}%字典

6        for j in range(len(s)): %遍历字符串

7            if s[j] in pd:

8                i=max(pd[s[j]],i) %若是遇见重复字符，调整到最近的重复字符位置

9            ans=max(ans,j-i+1) %计算字串长度，取最大值

10      pd[s[j]]=j+1 %加入键值对

11      return ans  

执行过程是这样的：

举个例子abcabcd：那么遍历的时候

i：    0 0 0 1 2 3 3

str： a b c a b c d

j：    0 1 2 3 4 5 6

pd[s[j]]:1 2 3 4 5 6 7 

这段代码是参考别人的解答，个人觉得很好，于是拿来学习下：

        这里在学习的时候有疑问的地方，第8行，为什么尾部的位置还是重复字符的位置，而不是前面一个字符的位置，在计算长度的时候也是对的，后来发现是第10行j+1的作用。而且这个+1是有说法的，为了防止“ ”的情况发生，因为在s=“ ”的时候，输出的是0，是不对的，按理要输出1的，是因为range（len（s）)=[0,1),j在遍历的时候只是遍历到0，因此输出的是0。这里+1避免了这种特殊情况发生。

参考

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

评论区的回答让我受益匪浅！

记录自己，生生不息