给定一个字符串 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(∣Σ∣),其中 Σ 是字符集。空间复杂度主要取决于哈希集合,哈希集合中每个字符最多出现一次。