问题描述：

        在一个字符串中找到没有重复字符子串中最长的长度。
例如:
        abcabcbb没有重复字符的最长子串是abc，长度为3
        bbbbb，答案是b，长度为1
        pwwkew，答案是wke，长度是3
要求:答案必须是子串，"pwke" 是一个子字符序列但不是一个子字符串。

思路：

思路一：暴力法，逐步检查所有的子字符串，找到最大不重复子字符串。

        时间复杂度：O(n^3)

        空间复杂度：O(min(m,n)), 需要O(K)的空间，其中K表示set的大小，取决于字符串n的大小以及字符集/字母m的大小。

思路二：滑动窗口， 如果我们已经确定了索引i到j-1之间的子串s(i,j-1)没有重复子字符串, 那我们只需要判断字符s[j]是否已经存在子串s(i,j-1)中。要检查一个字符是否已经存在在子字符串中，可以通过使用HashSet作为滑动窗口， 可以使用O(1)的时间来完成。

        回到我们的问题，我们使用HashSet将字符存储在当前窗口[i,j) （开始i=j）,然后我们向右滑动索引j，如果s[j]没在HashSet中，我们继续向右滑动j。 直到s[j]已经存在HashSet中，我们当前找到的最长子字符串就是i开始到j-1的一段字符串。如果对所有的i都这样操作，就可以找到答案。

        时间复杂度： O(2n) = O(n),在最糟糕的情况下i和j都访问了n次 。

        空间复杂度：O(min(m,n)),滑动窗口需要O(K)的空间，其中K表示set的大小， 取决于字符串n的大小以及字符集/字母m的大小。

思路三：优化的滑动窗口，上述的方法最多需要2n个步骤，其实可以优化到n个步骤 我们可以定义字符到索引的映射，而不是使用集合判断一个字符是否存在。

        当我们找到重复字符时，我们可以直接跳过该窗口。 也就是说，如果s[j]在子字符串[i,j-1)范围内与s[J]重复，我们不需要逐渐增加i，我们可以直接跳过s[i,J]范围内的所有元素，即将i变成J+1。

        时间复杂度：O(n)

        空间复杂度：O(min(m,n)),m是字符集的大小,set的大小取决于字符串n的大小以及字符集/字母m的大小。

思路四：利用整数数组作为直接访问表来替换Map。

        时间复杂度：O(n)

        空间复杂度：O(m),m是字符集的大小

代码

思路一代码

	public static int lengthOfLongestSubstring1(String s) {int n = s.length();int ans = 0;String maxson = null;for (int i = 0; i < n; i++) {for (int j = i + 1; j <= n; j++) {if (allUnique(s, i, j)) {
//					ans = Math.max(ans, j - i);if (j - i > ans) {ans = j - i;maxson = s.substring(i, j);}}}}System.out.println(maxson);return ans;}public static boolean allUnique(String s, int start, int end) {Set set = new HashSet<>();for (int i = start; i < end; i++) {Character c = s.charAt(i);if (set.contains(c)) {return false;}set.add(c);}return true;}

思路二代码

		public static int lengthOfLongestSubstring2(String s) {int n = s.length();Set set = new HashSet<>();String maxson = null;int ans = 0, i = 0, j = 0;while (i < n && j < n) {if (!set.contains(s.charAt(j))) {set.add(s.charAt(j++));
//				ans = Math.max(ans, j - i);if (j - i > ans) {ans = j - i;maxson = s.substring(i, j);}} else {set.remove(s.charAt(i++));}}System.out.println(maxson);return ans;}

思路三代码

	public static int lengthOfLongestSubstring3(String s) {int n = s.length();int ans = 0, i = 0, j = 0;String maxson = null;Map map = new HashMap<>();for (i = 0, j = 0; j < n; j++) {if (map.containsKey(s.charAt(j))) {i = Math.max(map.get(s.charAt(j)) + 1, i);}
//			ans = Math.max(ans, j - i);if (j - i + 1 > ans) {ans = j - i +1 ;maxson = s.substring(i, j+1);}map.put(s.charAt(j), j);}System.out.println(maxson);return ans;}

思路四代码

	public static int lengthOfLongestSubstring4(String s) {int n = s.length();int[] index = new int[128];int ans = 0;String maxson = null;for (int j = 0, i = 0; j < n; j++) {i = Math.max(index[s.charAt(j)], i);
//			ans = Math.max(ans, j-i+1);if (j - i + 1 > ans) {ans = j - i + 1;maxson = s.substring(i, j + 1);}index[s.charAt(j)] = j + 1;}System.out.println(maxson);return ans;}