这是悦乐书的第341次更新，第365篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Medium级别的第2题Longest Substring Without Repeating Characters（顺位题号是3）。给定一个字符串，找到最长无重复字符子字符串的长度。例如：
输入：“abcabcbb”
输出：3
说明：答案是“abc”，长度为3。
输入：“bbbbb”
输出：1
说明：答案是“b”，长度为1。
输入：“pwwkew”
输出：3
说明：答案是“wke”，长度为3。请注意，答案必须是子字符串，“pwke”是子序列而不是子字符串。
02 第一种解法
暴力解法，使用双指针和HashSet。
每次选取一个字符，从该字符开始往后遍历，存入HashSet中去，借助HashSet来判断是否重复出现，如果遇到重复字符，就结束循环，计算起始索引的长度，然后将HashSet清空，继续循环，再从第二个字符开始遍历，直到处理完所有字符。
此解法的时间复杂度是O(N^2)，最坏情况下时间复杂度是O(N^3)，因为HashSet的contains方法；空间复杂度是O(N)。
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<Character>();
int n = s.length(), left = 0, right = 0;
int result = 0;
for (int i=0; i<n; i++) {
left = i;
right = i;
while (right < n && !set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
}
result = Math.max(result, right-left);
set.clear();
}
return result;
}03 第二种解法
针对第一种解法，我们还可以将HashSet换成数组，用数组来判断字符是否重复出现，其他思路一样。
public int lengthOfLongestSubstring2(String s) {
int[] set = new int[256];
int n = s.length(), left = 0, right = 0;
int result = 0;
for (int i=0; i<n; i++) {
left = i;
right = i;
while (right < n && ++set[s.charAt(right)] < 2) {
right++;
}
result = Math.max(result, right-left);
// 将数组元素值全部重置为0
Arrays.fill(set, 0);
}
return result;
}04 第三种解法
滑动窗口算法。
此解法和上面的第一种解法有点类似，使用两个变量，一左一右，像窗口一样滑动，遇到重复值时，就将左边的一个字符从HashSet中移除，直到遍历完所有字符。
此解法的时间复杂度是O(N)，最坏情况下时间复杂度是O(N^2)，因为HashSet的contains方法；空间复杂度是O(N)。
public int lengthOfLongestSubstring3(String s) {
Set<Character> set = new HashSet<Character>();
int n = s.length(), left = 0, right = 0;
int result = 0;
while (left < n && right < n) {
if (!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
result = Math.max(result, right-left);
} else {
set.remove(s.charAt(left));
left++;
}
}
return result;
}05 第四种解法
使用索引值来判断，同时将HashSet换成256大小的数组。
public int lengthOfLongestSubstring4(String s) {
int[] set = new int[256];
int n = s.length(), i = 0, j = 0;
int result = 0;
while (i < n && j < n) {
i = Math.max(set[s.charAt(j)], i);
result = Math.max(result, j-i+1);
set[s.charAt(j)] = j+1;
j++;
}
return result;
}06 小结
算法专题目前已连续日更超过六个月，算法题文章210+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，好看、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
