问题简介:求给定字符串中最长的字符不重复的字符串的长度
问题详解:
给定一个字符串,寻找给定字符串中包含的最长的字符不重复的字符串的长度
注：答案必须是子字符串,不是子序列
是连续的字符不重复的字符串,不是所有不重复字符
举例:
1.
输入: “abcabcbb”
输出: 3
解释: 结果是 “abc”, 长度是 3
2.
输入: “bbbbb”
输出: 1
解释: 结果是 “b”,长度是 1
3.
输入: “pwwkew”
输出: 3
解释: 结果是 “wke”,长度是 3
JAVA 实现方法一：笨方法遍历（第一次愚蠢实现不推荐）
官方实现一 : Brute Force
简介：
逐个检查所有子字符串，看它是否没有重复的字符。
算法：
写一个方法 boolean allUnique(String substring),如果子字符串中的字符都是唯一的,则返回true,否则返回false.我们可以遍历给定字符串s的所有可能的子字符串并调用函数allUnique(),如果结果是true,那么我们更新子字符串的最大长度.
现在让我们填补缺少的部分：
复杂度分析：
时间复杂度 : 两层O(n3)：main()中两层遍历,方法中还有一层遍历.
空间复杂度 : O(min(n,m))：取决于字符串长度
官方实现二 : Sliding Window
滑动窗口是数组/字符串问题中常用的抽象概念。窗口是数组/字符串中的一系列元素，通常由开始和结束索引定义，即[i，j].
使用HashSet将字符存储在当前窗口[i，j]中(最初j = i)然后我们将索引jjj向右滑动,如果它不在HashSet中,我们进一步滑动j,这样做直到 s [j] 已经在HashSet中.此时,我们发现没有重复字符的子字符串的最大大小以索引i开头,为所有i执行此操作,会得到答案
复杂度分析;
时间复杂度 : O(n)：一层循环
空间复杂度： O(min(m,n))
官方实现三 : Sliding Window Optimized
定义字符到其索引的映射,而不是使用一个集来判断字符是否存在。,然后我们可以在找到重复的字符时立即跳过字符.
原因是，如果s [j] 在[i,j] 的范围内具有索引j的重复,我们不会需要一点一点地增加i,我们可以跳过[i,j] 范围内的所有元素,并让i直接为j+ 1
还可以假设ASCII 128
以前的实现都没有对字符串s的字符集进行假设。
如果我们知道charset相当小，我们可以用整数数组替换Map作为直接访问表。
常用的表有：
int[26] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’
int[128] for ASCII
int[256] for Extended ASCII
复杂度分析：
时间复杂度 : O(n).
空间复杂度(HashMap) : O(min(m,n)).
空间复杂度(Table): O(m).
小提示：
String的三种方法 indexOf(),lastIndexOf(),subString()