Java函数实现字符串中最长连续不重复子串的长度计算方法
发布时间:2023-07-03 01:54:31
要实现字符串中最长连续不重复子串的长度计算方法,可以使用滑动窗口的思想来解决。
滑动窗口是一种解决数组/字符串问题的有效方法。使用两个指针来表示窗口的左右边界,通过移动右指针来扩大窗口,移动左指针来缩小窗口,从而得到我们想要的结果。
具体步骤如下:
1. 定义一个HashMap来存储字符和它们在字符串中最后一次出现的位置。
2. 初始化窗口的左指针和最长不重复子串的长度,都为0。
3. 遍历字符串,将相应的字符和它们的位置存储在HashMap中。
4. 当遇到重复字符时,更新窗口的左指针,使其指向重复字符的下一个位置。
5. 计算当前窗口的长度,并更新最长不重复子串的长度。
6. 最后返回最长不重复子串的长度。
下面是一个Java函数实现的示例代码:
public static int longestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
HashMap<Character, Integer> map = new HashMap<>();
int left = 0;
int maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c)) {
// 更新窗口的左指针
left = Math.max(left, map.get(c) + 1);
}
// 更新字符的最后一次出现的位置
map.put(c, right);
// 计算当前窗口的长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
测试代码如下:
public static void main(String[] args) {
String s = "abcabcbb";
int maxLength = longestSubstring(s);
System.out.println("最长不重复子串的长度为:" + maxLength);
}
执行结果为:
最长不重复子串的长度为:3
注意:在这个示例中,我们假设字符串只包含ASCII字符。如果字符串包含Unicode字符,需要使用HashMap<Character, Integer>来存储字符和它们的位置。
