题目描述

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

示例：

给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。

给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。

给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

我的解法——DP（AC）

一个子串不可能出现重复的字符，那么我们可以用两个指针，一个指针用来遍历字符串，两个指针之间保持无重复字符，那么两个指针之间的长度即最大子串的长度。当发现有重复的字符时，另一个指针指向这个字符上一次出现的位置的下一个字符，继续遍历，直到找到最长子串。
时间复杂度O(n2)，空间复杂度O(n)
Beat 75%

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        l = 0
        r = length - 1
        
        while(l <= r):
            print(str(l) + ' ' + str(r),)
            mid = int((r - l)/2 + l)
            if(nums[mid] <= nums[r]): # 右面sorted
                if(target == nums[mid]):
                    return mid
                elif(target > nums[mid] and target <= nums[r]):
                    l = mid + 1
                else:
                    r = mid - 1
            else: # 左面sorted
                if(target == nums[mid]):
                    return mid
                elif(target < nums[mid] and target >= nums[l]):
                    r = mid - 1
                else:
                    l = mid + 1
        return -1

最优解法——DP+hashset

加一个hashset，就能保证时间复杂度O(n)
- 使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引i开头。如果我们对所有的i这样做，就可以得到答案。 =>这里是不断固定左边，滑动右边，和我的方法差不多。
- 上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。当我们找到重复的字符时，我们可以立即跳过该窗口。也就是说，如果 s[j]在 [i, j) 范围内有与 j’重复的字符，我们不需要逐渐增加i 。我们可以直接跳过 [i，j′] 范围内的所有元素，并将i变为 j’ + 1。
时间复杂度O(n)，空间复杂度O(n)。

参考答案

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