文章目录
- 一、题目描述？
- 二、题解
- 方案一：容易理解（时间复杂度O(n)）
- 方案二：滑动窗口（时间复杂度O(n)）
一、题目描述？
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
二、题解
方案一：容易理解（时间复杂度O(n)）
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int start=0,max=0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(map.containsKey(c)){
start=Math.max(start,map.get(c)+1);
}
map.put(c,i);
max=Math.max(max,i-start+1);
}
return max;
}
-
HashMap<Character, Integer> map = new HashMap<>();创建一个HashMap，用于存储字符及其最后一次出现的位置。
-
int max = 0;: 用于记录最长子串的长度。
-
int start = 0;: 用于记录当前子串的起始位置。
-
for (int i = 0; i < s.length(); i++) {: 遍历输入字符串。
-
char ch = s.charAt(i);: 获取当前遍历到的字符。
-
if (map.containsKey(ch)) { … }: 如果当前字符已经在子串中出现过。
-
start = Math.max(map.get(ch) + 1, start);: 更新子串的起始位置，确保不包含重复字符。
-
max = Math.max(max, i - start + 1);: 计算当前子串的长度并更新最大长度。
-
map.put(ch, i);: 将字符及其位置放入HashMap。
-
最后返回最长子串的长度 max。
方案二：滑动窗口（时间复杂度O(n)）
public int lengthOfLongestSubstring(String s) {
Set<Character> occ = new HashSet<Character>();
int n = s.length();
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
occ.add(s.charAt(rk + 1));
++rk;
}
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
这段代码使用了滑动窗口的思想。
- 初始化一个哈希集合 occ，用于记录每个字符是否出现过。
- 定义两个指针 rk 和 i，初始时 rk 为 -1，i 为 0。rk 代表窗口的右边界，i 代表窗口的左边界，初始时窗口大小为 0。
- 开始遍历字符串 s 的每个字符：
- 如果 i 不等于 0，说明窗口已经开始移动了，我们需要将窗口左边界向右移动一格，这时候就需要将原来窗口左边界的字符从哈希集合中移除。
- 在右边界 rk 小于字符串长度 n 且当前字符 s.charAt(rk + 1) 不在哈希集合中时，循环执行以下操作：
- 将当前字符 s.charAt(rk + 1) 添加到哈希集合 occ 中。
- 将右边界 rk 右移一格。
- 计算当前窗口大小，并更新最长子串长度 ans。
- 返回最长子串长度 ans。
