题目
1 | ''' |
给定一个字符串,求其不重复的最长子字符串的长度。
分析
设置一个头指针和尾指针,用一数组存储已经出现的字符,每次循环尾指针向后移动一位,将新出现的元素加入到数组中,如果新进元素在书中出现,定位到上次出现的位置,将数组切片后,组成新的数组。头指针设置为上一次元素出现的位置的后一位,循环这个过程。如果不存在,判断当前数组的长度是否大于当前最大长度,大的话新的数组长度为最大长度, 否则最大长度不变。
代码
1 | if len(s) <= 1: |
更进一步
O(n)算法的本质是 查找新出现的元素是否在以前出现过,如果出现过,则判断尾指针和头指针的距离是否大于当前保存的最大长度,是则更新最大长度,否则,将头指针移到上次出现的位置的下一个位置。
新代码
1 | start = maxl = 0 |
代码简洁度是不是提升了一个层次呢?