题目要求:
给定一个字符串 s
,请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 10^4
s
由英文字母、数字、符号和空格组成
题解:
import java.util.Arrays;
class Solution {
public int lengthOfLongestSubstring(String s) {
// 检查字符串是否为空或长度为0
if (s == null || s.length() == 0) {
return 0; // 如果是空字符串,返回0
}
// 将字符串转换为字符数组
char[] arr = s.toCharArray();
// 用于记录每个字符出现次数的数组
int[] n = new int[1000]; // 假设字符集的大小足够大
int result = 0; // 记录最长无重复字符子串的长度
int j = 0; // 滑动窗口的起始位置
// 遍历字符数组
for (int i = 0; i < arr.length; i++) {
n[arr[i]]++; // 记录当前字符的出现次数
// 如果当前字符出现次数超过1,表示有重复字符
while (n[arr[i]] > 1) {
n[arr[j]]--; // 减少起始字符的计数
j++; // 移动起始位置以排除重复字符
}
// 更新最长无重复字符子串的长度
result = Math.max(result, i - j + 1);
}
return result; // 返回最长无重复字符子串的长度
}
}
代码解释
空字符串检查:
if (s == null || s.length() == 0) { return 0; }
- 如果输入字符串
s
为空或长度为 0,直接返回 0,因为没有可处理的字符。
- 如果输入字符串
字符串转化为字符数组:
char[] arr = s.toCharArray();
- 将字符串
s
转换为字符数组arr
,以便于后续处理。
- 将字符串
字符计数数组:
int[] n = new int[1000];
- 创建一个整型数组
n
用于记录每个字符的出现次数。这里假设字符集的大小足够大(如 ASCII 字符集)。
- 创建一个整型数组
初始化变量:
int result = 0; // 最长无重复子串的长度 int j = 0; // 滑动窗口的起始位置
遍历字符数组:
for (int i = 0; i < arr.length; i++) { n[arr[i]]++; // 记录当前字符的出现次数
- 使用
for
循环遍历字符数组arr
,并增加当前字符的计数。
- 使用
处理重复字符:
while (n[arr[i]] > 1) { n[arr[j]]--; // 减少起始字符的计数 j++; // 移动起始位置以排除重复字符 }
- 如果当前字符的计数大于 1,说明出现了重复字符,则进入
while
循环,减少arr[j]
的计数,并移动j
,以确保窗口内的字符都是唯一的。
- 如果当前字符的计数大于 1,说明出现了重复字符,则进入
更新最长无重复子串长度:
result = Math.max(result, i - j + 1);
- 计算当前无重复子串的长度(
i - j + 1
),并更新result
,保持记录最长的长度。
- 计算当前无重复子串的长度(
返回结果:
return result;
- 方法结束时返回最长无重复字符子串的长度
result
。
- 方法结束时返回最长无重复字符子串的长度
注意事项
- 数组越界:在
for
循环中,arr.length()
应为arr.length
,因为arr
是字符数组,不是字符串。 - 字符集大小:
int[] n = new int[1000];
假设字符集足够大,实际上对于 ASCII 字符集,可以使用int[128]
或int[256]
来节省空间。
示例输入
假设我们的输入字符串是:
s = "abcabcbb"
初始化
字符数组转换:
char[] arr = s.toCharArray(); // arr = ['a', 'b', 'c', 'a', 'b', 'c', 'b', 'b']
字符计数数组:
int[] n = new int[1000]; // 用于记录字符出现次数
初始化变量:
int result = 0; // 最长无重复子串长度 int j = 0; // 滑动窗口的起始位置
遍历字符数组
我们将逐步遍历字符数组 arr
,并记录字符出现的次数,同时更新最长无重复子串的长度。
过程演示
i = 0,字符
arr[0] = 'a'
:n['a']++
->n['a'] = 1
result = Math.max(result, 0 - 0 + 1) = 1
(当前子串 “a”)
i = 1,字符
arr[1] = 'b'
:n['b']++
->n['b'] = 1
result = Math.max(result, 1 - 0 + 1) = 2
(当前子串 “ab”)
i = 2,字符
arr[2] = 'c'
:n['c']++
->n['c'] = 1
result = Math.max(result, 2 - 0 + 1) = 3
(当前子串 “abc”)
i = 3,字符
arr[3] = 'a'
:n['a']++
->n['a'] = 2
(出现重复)- 进入 while循环,n[‘a’] > 1:
- 第一次循环:
n['a']--
->n['a'] = 1
j++
->j = 1
(窗口变为 “bc”)
- 第二次检查
while
条件:n['a'] > 1
不成立,跳出循环。
- 第一次循环:
result = Math.max(result, 3 - 1 + 1) = 3
(当前子串 “abc”)
i = 4,字符
arr[4] = 'b'
:n['b']++
->n['b'] = 2
(出现重复)- 进入 while循环,n[‘b’] > 1:
- 第一次循环:
n['b']--
->n['b'] = 1
j++
->j = 2
(窗口变为 “c”)
- 第二次检查
while
条件:n['b'] > 1
不成立,跳出循环。
- 第一次循环:
result = Math.max(result, 4 - 2 + 1) = 3
(当前子串 “abc”)
i = 5,字符
arr[5] = 'c'
:n['c']++
->n['c'] = 2
(出现重复)- 进入 while循环,n[‘c’] > 1:
- 第一次循环:
n['c']--
->n['c'] = 1
j++
->j = 3
(窗口变为 “a”)
- 第二次检查
while
条件:n['c'] > 1
不成立,跳出循环。
- 第一次循环:
result = Math.max(result, 5 - 3 + 1) = 3
(当前子串 “abc”)
i = 6,字符
arr[6] = 'b'
:n['b']++
->n['b'] = 2
(出现重复)进入 while循环,n[‘b’] > 1
:
- 第一次循环:
n['a']--
->n['a'] = 0
j++
->j = 4
(窗口变为 “b”)
- 第二次检查
while
条件:n['b'] > 1
不成立,跳出循环。
- 第一次循环:
result = Math.max(result, 6 - 4 + 1) = 3
(当前子串 “bc”)
i = 7,字符
arr[7] = 'b'
:n['b']++
->n['b'] = 3
(出现重复)- 进入 while循环,n[‘b’] > 1:
- 第一次循环:
n['b']--
->n['b'] = 2
j++
->j = 5
(窗口变为 “c”)
- 第二次检查
while
条件:n['b'] > 1
不成立,跳出循环。
- 第一次循环:
result = Math.max(result, 7 - 5 + 1) = 3
(当前子串 “bc”)
最终结果
在遍历完整个字符串后,result
的值是 3
,表示最长无重复字符子串的长度为 3
(例如 “abc”)。