Leetcode-3解题思路及总结

无重复字符的最长子串
给定1个字符串，请你找出其中不含有重复字符的最长子串的长度。

输入：abcabcbb
输出：3
输入：bbbb
输出：1
输入：pwwkew
输出：3

分析：题目要求两点，1是无重复，2是子串。其中无重复需要考虑到查找；子串则是指连续的序列。
解法一：双指针法
使用两个指针，一前一后，若后指针的后一个元素不在两个指针界定的子串，则后指针向后移动，直至发现重复字符，计算当前两个指针界定子串的长度来更新最佳答案。然后找到当前后指针后一个元素在两个指针界定的子串中出现的位置，前指针直接移动到该位置后一个元素，后指针则正常向后移动。
以"pwwkew"为例，两个指针分别为i和j。
a) 初始状态i=0，j=1。
b) 保持i不变，指针j向后移动到j=2时，发现重复元素。当前两指针界定的子串为"pw"，长度为j-i=2，j所在位置元素在该子串中出现的位置为t=1。
c) 更新i，j的位置，使i+=(t+1)，i=2，j+=1，j=3。
d) 保持i不变，指针j向后移动到j=5时，发现重复元素。当前两指针界定的子串为"wke"，长度为j-i=3，j所在位置元素在该子串中出现的位置为t=0。
e) 更新i，j的位置，使i+=(t+1)，i=3，j+=1，j=6。
f) 指针j已经超过字符串的长度，终止循环，当前两指针界定的子串为"kew"，长度为j-i=3
程序运行过程中，总共找出满足条件的子串有3个，分别是："pw"，"wke"，"kew"。其中长度最长为3。
代码如下：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or len(s) == 0:
            return 0
        if len(s) == 1:
            return 1
        n = len(s)
        i = 0
        j = i + 1
        res = 0
        while j < n:
            while j < n and s[i:j].find(s[j]) == -1:
                j += 1
            if j - i > res:
                res = j - i
            if j < n:
                i += (s[i:j].find(s[j]) + 1)
            j += 1
        return res