本类型博客中的各算法的时间复杂度分析均为博主自己推算，本类型博客也是博主自己刷LeetCode的自己的一些总结，因此个中错误可能较多，非常欢迎各位大神在博客下方评论，请不吝赐教
一、问题
输入：一个字符串S输出：输出它的最长子串，该子串中不能包含相同的字符假设条件：字符串中的字符全部时ASCII吗，即编码值在0-128之间
二、输入输出示例
输入：“abcaa”输出：3，因为最长子串为"abc"
三、解法
最大不重复子串肯定包含在两个重复的字符之间，或者是某个字符跟开头或结尾之间的子串为最大不重复子串。因此在遍历时凡是第一次遇到重复的字符，其之间的子串必定是不重复的，此时判断该子串的长度，并与已经存在的最大长度作比较，然后新的子串必定位于重复的两个字符的左侧那个字符的右边，然后在右边继续使用之前的方法寻找子串即可。对于字符串的遍历为n，另一个部分则是在已经遍历的字符中的搜索当前字符，整体算法的时间复杂度为n*搜索算法的时间复杂度。
解法一：使用散列思想存储已经遍历的字符
解题思路：由于本题中的字符均为ASCII字符，因此最多有128种字符，创建一个长度为128的数组，每个位置存储该字符最近一次出现的索引，这样查找的时间复杂度为O(1)
package com.happy.leetcode.p3;
public class LongestSubstringWithoutRepeatingCharactersV1 {
public static void main(String[] args) {
String s = "au";
System.out.println(s);
System.out.println(new LongestSubstringWithoutRepeatingCharactersV1().lengthOfLongestSubstring(s));
}
public int lengthOfLongestSubstring(String s) {
if ("".equals(s.trim())) {
return 0;
}
int[] characters = new int[128];
int maxLength = 1;
int currentLength = 0;
int currentPos = -1;
for (int i = 0; i < s.length(); i++) {
int index = (int) s.charAt(i);
if (characters[index] > 0 && characters[index]>currentPos) {
currentLength = i - 1 - currentPos;
currentPos = characters[index] - 1;
if (maxLength < currentLength) {
maxLength = currentLength;
}
}
characters[index] = i + 1;
}
currentLength = s.length() - 1 - currentPos;
if (maxLength < currentLength) {
maxLength = currentLength;
}
return maxLength;
}
}
时间复杂度分析：n*1，时间复杂度为 O(n)
【注】该算法不是通用算法，由于散列算法的限制，因此该算法仅仅针对ASCII码字符
解法二：搜索采用Java的indexOf函数
解题思路：搜索时可以采用Java自带的indexOf函数，其实此函数实际为遍历一遍各个字符，找到想等的就返回索引
package com.happy.leetcode.p3;
public class LongestSubstringWithoutRepeatingCharactersV2 {
public static void main(String[] args) {
String s = "cddba";
System.out.println(s);
System.out.println(new LongestSubstringWithoutRepeatingCharactersV2().lengthOfLongestSubstring(s));
}
public int lengthOfLongestSubstring(String s) {
if ("".equals(s.trim())) {
return 0;
}
int maxLength = 1;
int currentLength = 0;
int currentPos = 0;
for (int i = 0; i < s.length(); i++) {
int index = s.indexOf(s.charAt(i), currentPos);
if (index >= 0 && index < i) {
currentLength = i - currentPos;
currentPos = index + 1;
if (maxLength < currentLength) {
maxLength = currentLength;
}
}
}
currentLength = s.length() - currentPos;
if (maxLength < currentLength) {
maxLength = currentLength;
}
return maxLength;
}
}
时间复杂度分析：indexOf的时间复杂度为n，因此总的时间复杂度为
O(n^2)
