题目：
题解：
1、滑动窗口 + 哈希表
解题思路：
- 滑动窗口，用set维护一个不重复的窗口，如果已经包含该字符，将该字符相等的字符之前的以及此字符元素全部移除，然后记录set的大小最大的就是最长不含重复字符的子字符串数。
复杂度分析：
- 时间复杂度O(N)：其中 N 是字符串的长度。
- 空间复杂度O(∣Σ∣)：，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// 滑动窗口 + 哈希表
class Solution {
public int lengthOfLongestSubstring(String s) {
// 滑动窗口，用set维护一个不重复的窗口
HashSet<Character> set = new HashSet<>();
int res = 0;
int l = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 如果已经包含c，将与c相等的字符之前的元素以及此字符元素全部移除
while(set.contains(c)) {
set.remove(s.charAt(l++));
}
set.add(c);
// 或者这样写 res = Math.max(res,set.size());
res = Math.max(res,i - l + 1);
}
return res;
}
}
2、动态规划
总体基本思路：
2.1 动态规划 + 哈希表
解题思路：
- 哈希表统计： 遍历字符串 s 时，使用哈希表（记为 dic ）统计 各字符最后一次出现的索引位置 。
- 左边界 i 获取方式： 遍历到 s[j] 时，可通过访问哈希表 dic[s[j]] 获取最近的相同字符的索引 i 。
复杂度分析：
- 时间复杂度 O(N) ： 其中 N 为字符串长度，动态规划需遍历计算 dp 列表。
- 空间复杂度O(∣Σ∣)：，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// 动态规划 + 哈希表
class Solution2 {
public int lengthOfLongestSubstring(String s) {
// 定义map集合，用来存放s中字符的位置对应的索引
Map<Character, Integer> map = new HashMap<>();
// tmp是dp
int res = 0,tmp = 0;
for (int j = 0; j < s.length(); j++) {
int i = map.getOrDefault(s.charAt(j),-1);
map.put(s.charAt(j),j);
tmp = tmp < j - i ? tmp + 1 : j - i;
res = Math.max(res,tmp);
}
return res;
}
}
2.2 双指针 + 哈希表
解题思路：
复杂度分析：
- 时间复杂度 O(N) ： 其中 N 为字符串长度，动态规划需遍历计算 dp 列表。
- 空间复杂度O(∣Σ∣)：，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// 双指针 + 哈希表
class Solution3 {
public int lengthOfLongestSubstring(String s) {
// 定义map集合，用来存放s中字符的位置对应的索引
Map<Character, Integer> map = new HashMap<>();
// i 是左指针，j 是右指针
int res = 0, i = -1;
for (int j = 0; j < s.length(); j++) {
// 如果map中已有目前右指针指向的key，
// 左指针取（已有key的value和目前左指针）的最大值
// ，因为如果已有key的value在左指针的左边，说明已经有重复的了，移过去再算j - i 就不对了
if (map.containsKey(s.charAt(j))) {
i = Math.max(i,map.get(s.charAt(j)));
}
map.put(s.charAt(j),j);
res = Math.max(res,j - i);
}
return res;
}
}
2.3 可以以此为例子，做解析：
