Skip to content

Latest commit

 

History

History
14 lines (10 loc) · 1.27 KB

File metadata and controls

14 lines (10 loc) · 1.27 KB

分析字符串“abcabcbb”:

  • 第一个字符肯定不含重复,所以最长子串为“a”,长度为1,继续下一个字符
  • 字符b与a不重复,所以最长子串更新为“ab”,长度更新为2,继续下一个字符
  • 字符c与a,b都不重复,所以最长子串更新为“abc”,长度更新为3,继续下一个字符
  • 字符a与字符串"abc"中的字符a重复,所以如果存在一个包含当前字符a的子串,其长度大于“abc”,那么这个子串肯定不包含第一个字符a,所以去除第一个字符a,从子串“bca”继续分析
  • ...

上述步骤中隐含一定的规律:

  • 如果没有出现重复字符,这每次按1增加最长子串的长度
  • 如果出现重复字符,需要从原来最长子串中重复字符处截断,以截断位置后面的字符串为基础继续分析

使用一个数组作为hash_map记录字符最近一次出现的位置,没遍历到一个字符时,如果map中其位置为-1,表示这个字符之前未出现过,因此增加长度。如果出现过,并且这个字符出现在截断位置之前,那么说明这个字符并没有重复,因此也增加长度。如果出现过,但是在截断位置之后,说明发生重复,因此进行截断,并更新相应的变量