无重复字符的最宗子串

1、标题描述

给定一个字符串 s ，请你找出其中不含有重复字符的最宗子串的长度。

2、解答思路

本题的解答思路是滑动窗口。定义左右指针，分别控制字符串的左界限和右界限；由于必要添加、删除和查询元素，因此选用哈希集合Set作为存储字符串的结构。

• 若右指针所指元素在哈希集中有相同元素，则左指针右移，哈希集中取出左指针所指元素，循环直至哈希集中不包含与右指针所指元素相等的元素（循环的目的是与右指针所指元素相等的元素大概在哈希集的中间位置，必要循环遍历到该位置并且将其及左边的元素全部移除哈希集中）。
  
• 若若右指针所指元素在哈希集中没有相同元素，则右指针右移，且将该元素添加到哈希集中，注意更新最大长度。
  

1. class Solution {
2.     public int lengthOfLongestSubstring(String s) {
3.         int left=0,right=0,ans=0;
4.         // 哈希集合
5.         Set<Character> set = new HashSet<>();
6.         // 将字符串转换为数组来得到指定下标的元素
7.         char[] ss = s.toCharArray();
8.         // 扩展右边界
9.         for(right=0;right<s.length();right++){
10.             // 若set中存在和右指针相同的元素，则左指针右移
11.             while(set.contains(ss[right])){
12.                 set.remove(ss[left]);
13.                 left++;
14.             }
15.             // 添加当前右边界
16.             set.add(ss[right]);
17.             // 更新最大长度
18.             ans = Math.max(ans, right-left+1);
19.         }
21.         return ans;
22.     }
23. }

复制代码

  

• 存储字符串的结构利用哈希集更为方便。
  
• 取出指定下标的元素时必要将字符串转换为数组更方便实现。
  
• 时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。