题目出处
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
个人解法
思路：
拿到所有子串，先初步去重，再去除长度=1的字符串，然后再过滤出不含重复字符的子串(通过比较每一位数和别的位数不相等)，最后输出最长子串的长度
核心在于如何找出所有不含重复字符的子串（暴力求解）
代码示例：（Java）
public static int lengthOfLongestSubstring(String s) {
/**
* "abcabcbb"
* 子串：1位，2位，3位，4位，。。。最短1位，最长8位
* s.substring(0,1):a、s.substring(0,2):ab、s.substring(0,3):abc。。。s.substring(0,8):abcabcbb
* s.substring(1,2):b、s.substring(1,3):bc、s.substring(1,4)：bca。。。s.substring(1,8):bcabcbb
* s.substring(2,3):c、、s.substring(2,4):ca、s.substring(2,5):cab。。。s.substring(2,8):cabcbb
* 。。。。
* s.substring(7,8):b
*
*
*
*
*/
Set<String> strSet = new HashSet<>();//全部子字符串
int length = s.length();
for (int i = 0; i < length; i++) {
for (int j = i + 1; j <= length; j++) {
String substring = s.substring(i, j);
strSet.add(substring);
}
}
Set<String> newStrSet = strSet.stream().filter(o -> o.length() != 1).collect(Collectors.toSet());
//无重复字符的子串
Set<String> desStrSet = new HashSet<>();
for (String sub : newStrSet) {
int subLength = sub.length();
boolean isEquals = false;
for (int i = 0; i < subLength; i++) {
for (int j = i + 1; j < subLength; j++) {
if (sub.charAt(i) == sub.charAt(j)) {
isEquals = true;
break;
}
}
if (isEquals) {
break;
}
}
if (!isEquals) {
desStrSet.add(sub);
}
}
int maxLength = 0;
for (String s1 : desStrSet) {
if (s1.length() > maxLength) {
maxLength = s1.length();
}
}
return maxLength;
}
复杂度分析
官方解法
思路：
代码示例：（Java）
public static int lengthOfLongestSubstring1(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
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;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
复杂度分析
考察知识点
1.字符串、字符串子串 定义，操作
java.lang.String.substring(int, int)：从当前下标到第二个参数下标-1
java.lang.String.substring(int)：默认当当前下标到最后一位
2.set底层存储方式，使用set去重
3.java输出字符串指定位置的值：charAt
收获
1.善用debug（尤其是条件debug），可以解决很多问题
2.算法其实就是一个解决问题的思路，在代码中体现可能就是一个方法（函数）
当遇到一个算法题的时候，不要怕，首先要努力读懂题意，然后想解决方法（不止一种，不同方法之间的时间和空间复杂度可能不同）
其实抽象出来就是一个输入，一个输出
例如：把大象放冰箱里（先不用管该需求是否合理，是否现实，先想解决方法）
我们的输入就是：大象，冰箱 输出：就是把大象放冰箱里