给定一个字符串，请找出其中无重复字符的最长子字符串。
在线评测地址：领扣题库官网
样例 1:
输入: "abcabcbb"
输出: 3
解释: 最长子串是 "abc".样例 2:
输入: "bbbbb"
输出: 1
解释: 最长子串是 "b".解题思路
- 暴力解法时间复杂度较高，会达到O(n^3)，故而采取滑动窗口的方法降低时间复杂度。
- 我们使用两个指针表示字符串中的某个子串的左右边界。每步操作中，右指针向右移动一位，然后不断移动左指针，直到这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着以右指针结束的，不包含重复字符的最长子串。我们记录下这个子串的长度。
- 在枚举结束后，我们找到的最长的子串的长度即为答案。
算法流程
-
window是滑窗内字符的集合，初始化为空。从前向后移动滑窗，同时更新当前子串长度cur_len和最长子串长度max_len。当滑窗右端移动到字符ch：
- 如果ch已存在window中，那么从滑窗的左端起删除字符，直到删除ch。每删除一个字符cur_len减1。
- 将ch添加到window中，cur_len加1。
- 更新最长子串长度max_len。
- 返回max_len。
复杂度分析
- 时间复杂度：O(n)，n为字符串s长度。左指针和右指针分别会遍历整个字符串一次。
- 空间复杂度：O(|Σ|)。Σ为字符串s中出现的字符集。由于我们使用哈希表来存储子串的字符，因此空间复杂度为O(|Σ|)。
代码
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
HashSet<Character> window = new HashSet<Character>();
int left = 0, curLen = 0, maxLen = 0;
char[] sc = s.toCharArray();
for (char ch: sc) {
// 从前向后删除，直到删除了ch
while (window.contains(ch)) {
window.remove(sc[left]);
left ++;
curLen --;
}
// 添加ch
window.add(ch);
curLen ++;
// 更新长度
maxLen = Math.max(maxLen, curLen);
}
return maxLen;
}
}更多题解参考：九章官网solution
