给定一个字符串,求、中不包含重复字符的最长子串的长度。
"abcabcbb"
, 的答案是 "abc"
,长度为 3。
"bbbbb"
, 的答案是 "b"
,长度为 1。
"pwwkew"
, 的答案是 "wke"
,长度为 3。请注意,答案必须是 子字符串 , “pwke "
是 sub 的序列, 不是子字符串。
公共静态intlengthOfLongestSubstring(字符串s){ int开始,结束; 字符串数=“”; 字符串 str = ""; for(start=0;start){ for(end=start+1;end<=s.length();end++){ str = s.substring(start, end); if(结束== s.length()){ if(count.length() < str.length()){//比较长度 计数 = str; } 断; }其他{if(str.contains(s.substring(end, end+1))){//有重复的时候处理一下,跳出循环,让start++ if(count.length() < str.length()){//比较长度 计数 = str; } 断; } } } } returncount.length(); }
1。假设有一个函数allUnique(),可以检测到某个字符串的子串中所有字符都是唯一的(没有重复字符),那么问题的描述就可以实现:
公共 类解决方案 { 公共intlengthOfLongestSubstring(字符串s){ int n = s.length(); int ans = 0; 对于 (int i = 0; i < n; i++) 对于 (int j = i + 1; j <= n; j++) if (allUnique(s, i, j)) ans = Math.max(ans, j - i); 返回 ans; }public boolean allUnique(String s, int start, int 结束){ Setset = new HashSet<>(); for (int i = 开始; i < 结束; i++) { 字符 ch = s.charAt(i); if (set.contains(ch)) 返回 false; 设置.add(ch); } 返回真; } }
2。滑动窗口思路:如果子串s[i,j]确定了(假设代表字符串的第i个字符到第j-1个字符表示的子串),那么只需要比较s[j]只需要使用子字符串 s[i,j]
重复即可如果重复:记录此时滑动窗口的大小,与最大滑动窗口比较,并赋值。然后滑动窗口大小重新定义为1,头部位置不变,向右移动一个单位。
如果不重复:滑动窗口头不变,末尾+1,整个窗口增加1个单位。继续进行下一个比较。
公共 类解决方案 { 公共intlengthOfLongestSubstring(字符串s){ int n = s.length(); Setset = new HashSet<>(); int ans = 0, i = 0, j = 0; 同时 (i < n && j < n) {//尝试扩大范围[i,j] if (!set.contains(s.charAt(j))){ set.add(s.charAt(j++)); ans = Math.max(ans, j - i); } 其他 { set.remove(s.charAt(i++)); } } 返回 ans; } }
3、使用HashMap
公共 类解决方案 { 公共intlengthOfLongestSubstring(字符串s){ int n = s.length(), ans = 0; Mapmap = newHashMap<>(); //当前字符索引 //尝试扩大范围[i,j] for (int j = 0, i = 0; j < n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)), i); }ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } 返回 ans; } }
4、
公共 类解决方案 { 公共intlengthOfLongestSubstring(字符串s){ int n = s.length(), ans = 0; int[]索引=新int[128]; //当前字符索引 //尝试扩大范围[i,j] for (int j = 0, i = 0; j < n; j++) { i = Math.max(index[s.charAt(j)], i); ans = Math.max(ans, j - i + 1); 索引[s.charAt(j)] = j + 1; } 返回 ans; } }