一、题目
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
二、示例
示例 1:
【输入】s = "abcabcbb"
【输出】3
【解释】因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
【输入】s = "bbbbb"
【输出】1
【解释】因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
【输入】s = "pwwkew"
【输出】3
【解释】因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s由英文字母、数字、符号和空格组成
三、解题思路
3.1> 思路1：暴力破解
通过两层for循环可以实现暴力破解寻找无重复字符串，最外层i循环，作为每次生成子字符串的头节点；第二层j循环，每次从i位置开始，拼装子字符串。最后选择长度最长的作为返回值。具体逻辑如下图所示：
思路1：暴力破解
3.2> 思路2：滑动窗口
通过start指针和i指针，我们可以构造一个窗口，在窗口中的所有元素，有一个非常重要的特征，就是——都是无重复的。所以，在窗口内的元素，就不需要再遍历对比了。所以，当发现有重复元素的时候，我们直接赋值start = index(c) -1来实现start的跳跃。由于在整个窗口中，是以start开始以i结束的，所以，通过i - start就可以计算出无重复字符串长度。具体逻辑如下图所示：
思路2：滑动窗口
四、代码实现
4.1> 实现1：暴力破解
class Solution {
public int lengthOfLongestSubstring(String s) {
int result = 0, temp = 0;
Map<Character, Integer> map;
for (int i = 0; i < s.length(); i++) {
map = new HashMap();
temp = 0;
for (int j = i; j < s.length(); j++) {
if (map.get(s.charAt(j)) != null) {
break;
} else {
map.put(s.charAt(j), j);
result = Math.max(result, ++temp);
}
}
}
return result;
}
}
4.2> 实现2：滑动窗口
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] mark = new int[128];// ascii码
int start = 0, result = 0;
for (int i = start; i < s.length(); i++) {
if (mark[s.charAt(i)] - 1 >= start ) { // 遇到了重复值, 并且打点下标值不小于start指针下标
result = Math.max(result, i - start); // 计算当前不含重复字符的长度
start = mark[s.charAt(i)]; // 重置start指针
}
mark[s.charAt(i)] = i + 1;
}
return Math.max(result, s.length() - start);
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。
更多技术干货，欢迎大家关注公众号“爪哇缪斯”(o)/~ 「干货分享，每周更新」
题目来源：力扣（LeetCode）
