写点什么

力扣解题:第三题(个人思路整理)

发布于: 2020 年 11 月 06 日

题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。



解题思路

一步步拆解、补充,直到完整解题



1.首先想到的是需要循环整个字符串

class Solution {
int lengthOfLongestSubstring(String s) {
// 循环整个字符串
int len = s.length();
for (int i = 0; i < len; i++) {
}
return 0;
}
}



2.整个解题的过程大致是:

1)从最左边的字符开始与右边的字符一一比对,发现有重复的字符之后,计算当前子字符串的长度;

2)移动最左边的字符,重复1)过程,直到字符串的最右边结束,即循环整个字符串。

技巧:

a)在判断字符串重复字符的技巧,使用Set

b)移动过程中右指针始终向右移动,不需要循环,如同一个移动的窗口。

c)字符串循环开始时,需要从Set中移除上一个字符串中的字符

步骤:

1)初始化右指针、无重复子字符串长度、Set容器

2)当右指针未到字符串最后边,并且右指针所指字符不包含在子字符串时,继续循环操作

3) 计算当前子字符串的长度是否大于上次计算的字符串长度

4)从Set中移除上一个字符串中的字符



完整代码



class Solution {
int lengthOfLongestSubstring(String s) {
// 1)初始化右指针
int rk = 0;
// 1)初始化无重复子字符串长度
int subLen = 0;
// 1)初始化Set容器
Set<Character> subSet = new HashSet<>();
// 循环整个字符串
int len = s.length();
for (int i = 0; i < len; i++) {
// 4)从Set中移除上一个字符串中的字符
if (i != 0) {
subSet.remove(s.charAt(i - 1));
}
// 2)当右指针未到字符串最后边,并且右指针所指字符不包含在子字符串时,继续循环操作
while (rk < len && !subSet.contains(s.charAt(rk))) {
// 将右指针所指字符放入字符Set中
subSet.add(s.charAt(rk));
// 右指针向右移动
rk = rk + 1;
}
// 3) 计算当前子字符串的长度是否大于上次计算的字符串长度
subLen = Math.max(subLen, rk - i);
}
return subLen;
}
}



发布于: 2020 年 11 月 06 日阅读数: 22
用户头像

熟能生巧 2018.05.07 加入

Java 研发工程师

评论

发布
暂无评论
力扣解题:第三题(个人思路整理)