给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 请用java实现
时间: 2023-10-14 22:20:37 浏览: 43
可以使用滑动窗口算法来解决这个问题。
具体的,我们维护一个滑动窗口,其中的字符均不重复,我们用两个指针 left 和 right 分别表示窗口的左右边界。初始时,两个指针都指向字符串的开头。
然后,我们依次将 right 指针向右移动,如果遇到了重复字符,我们就将 left 指针向右移动,直到窗口中不再有重复字符。在移动过程中,我们记录窗口的长度,并且记录最长的长度。
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;
}
```
其中,set 表示滑动窗口中的字符集合,i 和 j 分别表示左右指针的位置,ans 表示当前最长的不重复子串长度。
时间复杂度为 O(n),空间复杂度为 O(min(n, m)),其中 m 是字符集的大小。
相关问题
给定一个字符串 s,请你找出其中不含有重复字符的 最长子串 的长度
给定一个字符串 s,我们需要找出其中不含有重复字符的最长子串的长度。可以使用滑动窗口的方法来解决这个问题。
滑动窗口是一种常用的解决子串或子数组问题的方法。它通过维护一个窗口,来遍历整个字符串。具体步骤如下:
1. 定义两个指针,left 和 right,分别表示窗口的左边界和右边界。
2. 初始化最长子串的长度为 0,定义一个集合 set 来存储窗口中的字符。
3. 遍历字符串 s,不断移动右指针 right,并将对应的字符加入到集合 set 中。
4. 如果集合 set 中已经存在当前字符,表示出现了重复字符,需要移动左指针 left,并将对应的字符从集合 set 中移除,直到集合 set 中不再包含重复字符。
5. 在每次移动左指针 left 和右指针 right 后,更新最长子串的长度为 max(maxLength, right - left + 1)。
6. 重复步骤 3-5,直到遍历完整个字符串 s。
最终得到的 maxLength 就是不含有重复字符的最长子串的长度。
给定一个字符串 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;
}
```
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)