给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。用java实现并详细解释
时间: 2023-02-23 15:32:35 浏览: 49
我建议使用滑动窗口的方法来实现。将一个长度为 n 的字符串 s 划分为 n+1 个窗口,每个窗口中都包含一个字符。然后,使用一个 HashSet 存储窗口中出现的字符,如果 HashSet 中出现重复字符,则将窗口左边界右移,直到不再出现重复字符,记录当前窗口的最大长度,然后继续向右移动窗口的右边界,重复上述操作,最后可以得到不含有重复字符的最长子串的长度。
相关问题
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度用java实现
可以使用滑动窗口算法来解决这个问题,具体步骤如下:
1. 定义一个哈希集合用于记录当前窗口中存在的字符。
2. 使用双指针 i 和 j 表示滑动窗口的左右边界,初始值都为 0。
3. 遍历字符串 s,每次移动右指针 j,并将对应的字符加入到哈希集合中。
4. 如果发现哈希集合中已经存在了 s[j] 这个字符,说明当前窗口中存在重复字符,需要移动左指针 i,并将对应的字符从哈希集合中删除,直到窗口中不再存在重复字符为止。
5. 每次移动左指针 i 和右指针 j 后都需要更新最长子串的长度。
下面是 Java 代码实现:
```java
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
```
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。用java实现并详细解释代码内容
答:解答这个问题可以使用滑动窗口算法,该算法主要使用两个指针i和j,分别指向字符串s的开始和结尾。然后遍历字符串s,若在 [i, j] 范围内发现重复字符,则调整i的位置,使其去除重复字符,并计算当前的最大长度,即 maxLen = max(maxLen, j - i + 1);同时移动j以指向下一个字符。在遍历结束后即可得出不含有重复字符的最长子串的长度。代码实现如下:int maxLen = 0;
int i = 0, j = 0;
while (j < s.length()) {
if (set.contains(s.charAt(j))) {
// 去重
set.remove(s.charAt(i++));
} else {
set.add(s.charAt(j++));
maxLen = Math.max(maxLen, j - i);
}
}
return maxLen;