题目：给定一个字符串，找出其中无重复字符串的最长子串长度。
例如 ：
输入：“abcabcbb”
输出： 3
说明： “abc”为其中的最长无重复子串，长度为3
题解：
- 使用两个指针，左指针指向当前子串起始下标，右指针指向当前子串尾部下标。右指针每移动一位，计算当前的子串长度。
- 在指针移动过程中，需要记录当前子串以存在的字符和下标，比如用Map存储。
- 当右指针每移动一次，需判断当前子串中是否已经存在当前指向的字符。若已存在，需将左指针移动到当当前字符的下标。再继续移动右指针，直至遍历完字符串。
题解代码如下：
public class Solution {
public static int lengthOfLongestSubstring(String s) {
int length = s.length();
int ans = 0;
// current index of character
Map<Character, Integer> map = new HashMap<>();
// try to extend the range [left, right]
int left = 0;
for (int right = 0; right < length; right++) {
Character c = s.charAt(right);
if (map.containsKey(c)) {
left = Math.max(map.get(c), left);
}
ans = Math.max(ans, right - left + 1);
map.put(c, right + 1);
}
return ans;
}
}
该题还另外一种更优解法，在上方解法中，借助了Map。但在使用Map的同时，也造成了性能的损耗。换个思路，因为给出的字符串中，均为英文字母，a-z或A-Z。其在ASCII表中，A-Z对应65-90，a-z对应97-122。因此可借助ASCII表，使用基本数据类型数据来代替Map。其做法如下：
public class Solution {
public static int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
// current index of character
int[] index = new int[128];
// try to extend the range [left, right]
for (int right = 0, left = 0; right < n; right++) {
// if index[s.charAt(right)] > left , means current char is repeat
left = Math.max(index[s.charAt(right)], left);
ans = Math.max(ans, right - left + 1);
index[s.charAt(right)] = right + 1;
}
return ans;
}
}