题目难度:Medium
题目要求:
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
##哈希集合
两个指针,分别表示子串的左右边界,
左指针不动,右指针不断右移,每次将一个字符加入哈希集合,并且判断,是否和原集合中的字符重复;
如果重复,就输出当前的非重复的字符长度,然后左指针右移一位,再寻找新的不重复的子串,
最后从所有不重复子串的长度中选出最长的长度返回。
// @lc code=start
class Solution {
public int lengthOfLongestSubstring(String s) {
//哈希集合,记录每个字符是否出现过
Setocc=new HashSet();
int n = s.length();
//右指针,初始值为-1,相当于在字符串的左边界的左侧,还没有开始移动
int rk=-1,ans=0;
for(int i=0;i
**复杂度分析:
时间复杂度:O(N),其中 N是字符串的长度。左指针和右指针分别会遍历整个字符串一次。空间复杂度:O(∣Σ∣),其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在[0,128) 内的字符,即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符,而字符最多有∣Σ∣ 个,因此空间复杂度为 O(∣Σ∣)。
**



