题目大意：给定一个字符串，找出不含有重复字符的最长子串的长度
解读：
1、给定abcabcbb，没有重复子串的最长子串是“abc”，那么长度就是3
2、给定bbbbb，最长子串就是“b”，长度就是1
3、给定pwwkew，最长子串就是"wke"，长度是3
注意：必须是一个子串"pwke",是子序列，而不是子串
思路：
滑动窗口
如果从索引i到j-1之间的子字符串s[s,j]已经被检查为没有重复字符串，那则只需要检查s[j]对应的字符是否存在与子字符串s[ij];
使用HashSet将字符存储在当前窗口[i,j),最初i=j.然后向右滑动索引j，如果它不在HashSet中，则继续滑动j。直到s[j]已经存在于HashSet中，此时，就找到没有重复字符的最长子串将会以所以i开头。
优化：如果s[j]在[i,j)的范围内有与k重复的字符，不需要逐渐增加i，而是直接跳过[i,k]范围内的所有元素，将i变成k+1就可以做到
实现：
字符串是由字符组成，而字符可以使用ASCII来替代，所以此处使用整数数组作为直接访问表来替换map
public class Solution{
public static void main(String[] argv){
String s = "abcabcbb";
int len = getMaxLongestStringLength(s);
}
public static int getMaxLongestStringLength(String s){
int[] index = new int[128];
int j = 0, i = 0, ans = 0;
int n = s.length();
for(j =0;j<n;j++){
i = Math.max(index[s.charAt(j)],i);
ans = Math.max(ans, j-i+1);
index[s.charAt(j)] = j+1;
}
return ans;
}
}
网友评论