# 原地址
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
# 思路分析(先简单看思路,然后看表格,看代码,最后在看一遍思路)
- 解法一:暴力判断法,需要用到map或者set判断是否重复
- 解法二:滑动窗格,先按照第一个进行滑动到最大,如果不满足后,从重复位置开始在开始滑动
- 解法三:动态规划,每遍历一个字母,都要判断当前字母位置与上一次出现重复字母位置的差
- 例如:abca中,遍历到abc,上一次重复字母的位置一直为0,当遍历到a的时候,上一次重复字母的位置就为1,因为第一次a的下标为1.
- 例如:abcbad,abc中,上一次重复字母为0,然后继续走发现b重复了,上一次的位置为2,所以可以计算出当前b和上一次b的距离为2,又因为abc中最大为3,所以目前最大还是3。然后继续走发现重复字母a,但是重复a的位置为1,最大的重复字母位置为2,所以还是用的重复字母b的位置,所以当前最大长度为(第二个a-重复字母b+1)=4-2+1=3,又因为最大长度为3,所以最大长度不更新。最后判断字母d,因为字母d不重复,所以直接计算最大长度=(d位置-重复字母b的位置+1)=5-2+1=4,最大长度4大于3,所以目前最大长度为4。
# 解法三 图像表示 abcbad
||数组下标 i|最大重复字母索引 j|最大长度max|map索引|
|-------|-------|-------|-------|-------|
|a|0|map中不重复,所以为0|max=i-j+1=1|1|
|b|1|map中不重复,所以为0|max=i-j+1=2|2|
|c|2|map中不重复,所以为0|max=i-j+1=3|3|
|b|3|b重复,索引为2|max=i-j+1=2|4|
|a|4|a重复,索引为1,但最大的为2,所以还是2|max=i-j+1=3|5|
|d|5|map中不重复,所以为2|max=i-j+1=4|6|
# 解法一
```java
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) return s.length();
int maxCount = 0;
for (int i = 0; i < s.length(); i++) {
Map map = new HashMap();
int count = 1;
char a = s.charAt(i);
for (int j = i - 1; j >= 0; j--) {
char b = s.charAt(j);
if (map.get(b) == null) {
map.put(b, b);
if (a == b) {
break;
} else {
count++;
}
} else {
break;
}
}
maxCount = maxCount >= count ? maxCount : count;
}
return maxCount;
}
}
```
# 解法三
```java
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap();
int maxCount = 0;
int repeatPosition = 0;
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i);
if (map.get(a) == null) {
} else {
repeatPosition = repeatPosition>=map.get(a)?repeatPosition:map.get(a);
}
// System.out.println(a + ":" + repeatPosition);
maxCount = maxCount >= (i - repeatPosition + 1) ? maxCount : (i - repeatPosition + 1);
map.put(a, i + 1);
}
return maxCount;
}
}
```

3. 无重复字符的最长子串