最长不含重复字符的子字符串
约 1024 字大约 3 分钟
题目：
输入一个字符串，找出字符串中最长的不含重复字符的子字符串，计算该子字符串的长度。假设字符串中的字符为“a~z”，例如 arabcacfr ，最长的字符串为 rabc 和 acfr ，长度为 4
思路：
采用暴力的方法，时间复杂度高度 n^3 ,显然是不可取的。
本题应该采用动态规划的方法来解决，时间复杂度只需要 n ,以及一个辅助的数组即可。
我们直接以 arabcacfr 为例子进行分析，从头开始遍历字符串的字符。
- 第一个字符 a ，此前 a 没有出现过，所以长度为 f(1) = 1，最长的子字符串是 a ;
- 第二个字符 r ，同样没出现过，所以 f(1) = 2 ,最长的子字符串是 ar ;
- 第三个字符 a ,因为 在第一个已经出现过了，且 在当前的最长字符串 ar 中，所以现在 f(2) = 2,最长子字符串更新为 ra；
- 第四个字符 b ,f（3） = 3，第五个字符 c ,f（4） = 4 ,此时最长子字符串为 rabc ；
- 第六个字符 a,在我们当前的最长子字符串中已经出现，所以 f（5） = 3，最长子字符串更新为 bca ;
- 第七个字符c,类似上面，所以 f（6） = 2，最长子字符串为 ac ;
- 第八个字符 f,没出现过 所以 f（7） = 3，最长子字符串更新为 acf
- 最后 一个字符 r，前面已经出现过，但是不在我们当前最长子字符串acf 中，所以 f（8） = 4，最长子字符串更新为acfr 。
分析到此结束，接下来我们如何去实现？
这就需要我们用到前面说的辅助数组 arr，我们用一个初始化的值全为负数的数组，以字符串中的字符temp 为下标进行标记，数组的值为该字符的位置 i 。当我们遍历到第 i 个字符，如果 arr[ temp ] 的值为负数，那么说明这个字符还未出现过；如果 arr[ temp ] 值不为负数，那么说明这个字符已经出现过。接下来我们要判断这个字符是否在我们当前统计的最长子字符串中。如果不在当前的子字符串中，那么 f( i） = f（i - 1）+ 1；如果在当前的最长子字符串中，就像上面的第4 、 5步，我们需要重新计算当前最长子字符串，也就是需要找到上一次出现该字符的位置，然后从它后面一位开始统计。
代码：
class Solution {
public static int getLongestSubStr(String str) {
if (null == str) {
return 0;
}
int[] arr = new int[26];
int max = 0;
int count = 0;
for (int i = 0; i < 26; i++) {
arr[i] = -1;
}
for (int i = 0; i < str.length(); i++) {
// ascii 相减，获取在数组 arr 中的位置 index
int index = str.charAt(i) - 'a';
// 获取位置 index 上是否有值，判断该字符是否存在
int value = arr[index];
if (value == -1) {
// 如果不存在，记录该字符在字符串中出现的位置(角标)
arr[index] = i;
// 长度增加
count++;
} else {
// 如果已存在
if (arr[str.charAt(i) - 'a'] != -1) {
if (i - value > count) {
//说明当前的字符str.charAt(i)上一次出现的位置在现在统计的子字符串前面，，对现在的统计没影响
count++;
} else {
//当前字符上一次出现的位置在统计之中，我们需要重新统计count即当前的最长子字符串
count = i - value;
}
// 更新上次出现的位置
arr[index] = i;
}
}
if (count >= max) {
max = count;
}
}
return max;
}
public static void main(String[] args) {
String str = "arabcacfr";
int length = getLongestSubStr(str);
System.out.println(length);
}
}
版权声明：本文为CSDN博主「luzi_这个人有点意思」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_34528297/article/details/72859450