题目描述:
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
解析:
滑动窗口(sliding window)
1.创建一个set
2.两个指针
第一个指针j指向字符串的开头
第二个指针i随着for循环遍历字符串
3.如果set里没有[i],说明目前为止还没有重复的字符,把s[i]添加到set里,
然后更新最大不重复字符的数量。
4.如果set里有s[i],则从set里开始删除s[j],并且递增j,再检查set里是否有s[i],
如此反复直到set里没有s[i]为止。
5.重复步骤3和4,知道遍历完整个字符串。
Java:
public int lengthOfLongestSubstring(String s) { if(s == null || s.length() == 0) { return 0; } HashSet<Character> set = new HashSet<>(); int j = 0, maxLength = 0; for(int i = 0; i < s.length(); i++) { if(!set.contains(s.charAt(i))) { set.add(s.charAt(i)); maxLength = Math.max(maxLength, set.size()); } else { while(set.contains(s.charAt(i))) { set.remove(s.charAt(j)); j++; } set.add(s.charAt(i)); } } return maxLength; }
JavaScript:
var lengthOfLongestSubstring = function(s) { if(s.length === 0) { return 0; } const set = new Set(); let j = 0, maxLength = 0; for(let i = 0; i < s.length; i++) { if(!set.has(s[i])) { set.add(s[i]); maxLength = Math.max(maxLength, set.size); } else { while(set.has(s[i])) { set.delete(s[j]); j++; } set.add(s[i]); } } return maxLength; };