转载请注明出处：
http://egoistk21.xyz/2016/09/06/Longest Substring Without Repeating Characters/
最长无重字符子串
给定一个字符串，找到最长子串的长度不重复的字符。
例子：
给定“abcabcbb”，答案是“abc”，它的长度为3。
给定“bbbbb”，答案为“b”，长度为1。
给定“pwwkew”，答案是“wke”，长度为3。
注意答案一定是一个字符串的长度，“pwke”是一个序列，而不是子串。
这是我第一遍刷算法题，也是第一遍刷Leetcode。碰到这个字符串的问题，一开始我有点懵，这对我太有难度了。但是我忍住没有去看Editorial，一点点自己码。嗯，这是一个好的开端。
题目要求我们获得最长无重子串，所以我从最长入手，用一个变量currLength从最长子串开始递减，再用两个变量i，j遍历currLength子串中是否有重复字符，若有则currLength自减，若无则返回currLength为最长无重子串的长度。若字符串本身长度小于2则直接返回字符串本身长度。但是测试数据的时候出现了问题，原来我忘了考虑currLength自减后，currLength长度的子串不止一个。比如“abcabcbb”的长度为8，它的长度为7的子串有“abcabcb”和“bcabcbb”，两个。所以我又加了一层循环用来滑动currLength的子串。
下面就是我的第一个方法：
public static int lengthOfLongestSubstring(String s) {
char c;
boolean flag = false;
int length = s.length(), currLength = 0;
if (length < 2) return length;
//滑动字符子串长度currLength
for (currLength = length; currLength > 1; currLength--) {
//滑动字符子串位置head
for (int head = 0; head <= length - currLength; head++) {
//滑动字符子串内遍历查询重复字符
for (int i = head; i < head + currLength - 1; i++) {
c = s.charAt(i);
for (int j = i + 1; j < head + currLength; j++) {
//如果遍历中遇到重复字符，则跳出循环，字符子串右移一位
if (c == s.charAt(j)) {
flag = true;
break;
}
}
if (flag) {
flag = false;
break;
}
//如果遍历结束,字符子串内无重复字符，返回当前长度currLength
if (i == head + currLength - 2) return currLength;
}
}
}
return currLength;
}
但是这段代码提交后被rejected了。原因是时间复杂度太大，当遇到字符串本身超长且最长无重子串较短时，所需计算时间太长。四层循环，时间复杂度为O(n^4)。所以我需要改进我的算法，从减少循环层数开始，我称之为更加线性化的算法。
这次我从第一个字符开始，用双指针的方法，双指针首先指向第m个和第n个字符（m<n），若不相同则尾指针右移；若相同则头指针右移跳出比较循环同时尾指针也右移，因为尾指针所指字符只和头指针所指字符相同，头指针所指字符和头指针与尾指针之间的字符都不相同。另外当遍历到最后一个字符的时候，返回maxLength和currLength中较长者。
代码如下：
public static int lengthOfLongestSubstring(String s) {
char c;
boolean flag = false;
int head = 0, tail = 1, curr, length = s.length(), currLength = 0, maxLength = 0;
if (length < 2) return length;
//线性遍历整个字符串s，每次遇到重复字符，记录当前无重字符子串长度并与maxLength比较取大，字符子串头部head右移一位
for (; head < length - currLength; head++) {
for (; tail < length; tail++) {
c = s.charAt(tail);
for (curr = head; curr < tail; curr++) {
if (c == s.charAt(curr)) {
currLength = tail - head;
maxLength = (maxLength > currLength)?maxLength:currLength;
head = curr + 1;//head重定位
//tail不重新赋值，也会自加，相当于++tail
flag = true;
break;
}
}
if (flag) {
flag = false;
continue;
}
if (tail == length - 1 && curr == tail) {
currLength = tail - head + 1;
return (maxLength > currLength)?maxLength:currLength;
}
}
}
return maxLength;
}
这次提交后总算accepted了，爽！
但是隐约中我觉得还有更好的算法，但是目前自己技术有限，等以后再来填坑～
谢谢阅读
