LeetCode[中等] 3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路：滑动窗口，设置左右指针left与right，maxLength存储长度
利用HashSet性质，存储滑动窗口中的字符
如果没有重复的，那么right继续向右滑动，并将该字符添加进HashSet中；如果重复了，left向右滑动，并不断将字符移出数组。
完成一次判断之后，更新最长字串长度
public class Solution {
public int LengthOfLongestSubstring(string s) {
HashSet<char> set = new HashSet<char>();
int left = 0, right = 0, maxLength = 0;
int length = s.Length;
while(right < length)
{
if(!set.Contains(s[right]))
{
set.Add(s[right]);
right++;
}
else
{
set.Remove(s[left]);
left++;
}
maxLength = Math.Max(maxLength, right - left);
}
return maxLength;
}
}复杂度分析
-
时间复杂度：O(n)，其中 n 是字符串 s 的长度。滑动窗口的左右端点最多各遍历字符串 s 一次。
-
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集。空间复杂度主要取决于哈希集合，哈希集合中每个字符最多出现一次。