3. 无重复字符的最长子串 布满荆棘的人生 2022-12-28 01:47 94阅读 0赞 # [3. 无重复字符的最长子串][3.] # ## 1、参考资料 ## https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ ## 2、题目要求 ## > **题目要求:** 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 > **示例 1:** 输入: `"abcabcbb"` 输出: `3` 解释: 因为无重复字符的最长子串是 `"abc"`,所以其长度为 `3`。 > **示例 2:** 输入: `"bbbbb"` 输出: `1` 解释: 因为无重复字符的最长子串是 `"b"`,所以其长度为 `1`。 > **示例 3:** 输入: `"pwwkew"` 输出: `3` 解释: 因为无重复字符的最长子串是 `"wke"`,所以其长度为 `3`。 请注意,你的答案必须是 子串 的长度,`"pwke"` 是一个子序列,不是子串。 ## 3、代码思路 ## 滑动窗口法:定义两个指针,`startIndex` 和 `endIndex` ,代表当前窗口的开始和结束位置,使用 `hashset`,当窗口中出现重复的字符时,`startIndex ++`没有重复时,`endIndex ++`,并更新长度的最大值,时间复杂度 `o(n)` > **举例说明:** 1. 比如 `"pwwkew "` 字符串 2. 初始时 `startIndex = 0` ,`endIndex = 0` ,均指向第一个字符串中第一个字符 3. `endIndex` 扫描到第一个字符 `'p'` ,发现 `HashSet` 中没有,添加至 `HashSet` 中,`endIndex` 后移 ![image-20200723094405548][] 4. `endIndex` 扫描到字符 `'w'` ,发现 `HashSet` 中没有,添加至 `HashSet` 中,`endIndex` 后移 ![image-20200723094627395][] 5. `endIndex` 扫描到字符 `'w'` ,发现 `HashSet` 存在该字符,尝试着将其从 `HashSet` 中删除 6. 为什么我要说尝试着删除?因为每次我们在 `HashSet` 中删除的是 `startIndex` 索引处的字符,这可能并不是与当前 `endIndex` 处字符互相重复的字符,比如 `"abcb"` 7. 删除字符后,`startIndex` 别忘了后移 8. 直到 `HashSet` 中不存在重复字符为止 ![image-20200723094757570][] 9. 执行上述删除操作后,`startIndex` 和 `endIndex` 均指向 `'w'` ,此时 `HashSet` 中没有 `'w'`(上一步给删了),将 `'w'` 添加至 `HashSet` 中, `endIndex` 后移 ![image-20200723095824347][] 10. 什么时候停止?`endIndex < str.length()` ,当 `endIndex` 扫描字符串最后一位后,`endIndex` 后移一位,此时 `endIndex == str.length()` ,说明字符串已经扫描完毕 ## 4、代码实现 ## 代码 public static void main(String[] args) { int max = maxSubStrLenWithNoRepearChar("pwwkew"); System.out.println(max); } public static int maxSubStrLenWithNoRepearChar(String str) { // 起始索引 int startIndex = 0; // 结束索引 int endIndex = 0; // 字符串长度 int strLen = str.length(); // HashSet 用于判断是否有重复字符 Set<Character> set = new HashSet<Character>(); // 无重复字符的字串的最大长度 int maxLength = 0; // 扫描到字符串结尾 while (endIndex < strLen) { // 如果 HashSet 中已经有此字符 if (set.contains(str.charAt(endIndex))) { set.remove(str.charAt(startIndex++)); } else { // 否则 HashSet 还没有此字符,向 HashSet 中添加此字符 set.add(str.charAt(endIndex++)); // 计算子串最大长度 maxLength = Math.max(maxLength, endIndex- startIndex); } } return maxLength; } [3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ [image-20200723094405548]: /images/20221120/215ba9b240b64bbaa74f536a0e1f521f.png [image-20200723094627395]: /images/20221120/e29edc507be947e181cefd0b6777a09b.png [image-20200723094757570]: https://img-blog.csdnimg.cn/img_convert/e25c4bc48a5162e70ed38bfc27a48da3.png [image-20200723095824347]: https://img-blog.csdnimg.cn/img_convert/db15fb0e7cd418ab91cc90423ef6d43f.png
还没有评论,来说两句吧...