【每日一题】LeetCode 3. 无重复字符的最长子串 TypeScript

【二刷】给定一个字符串s请你找出其中不含有重复字符的最长 子串的长度。示例 1:输入:s abcabcbb输出:3解释:因为无重复字符的最长子串是abc所以其长度为 3。注意 bca 和 cab 也是正确答案。示例 2:输入:s bbbbb输出:1解释:因为无重复字符的最长子串是b所以其长度为 1。示例 3:输入:s pwwkew输出:3解释:因为无重复字符的最长子串是wke所以其长度为 3。 请注意你的答案必须是子串的长度pwke是一个子序列不是子串。提示0 s.length 105s由英文字母、数字、符号和空格组成滑动窗口 哈希表1. 维护一个窗口[leftright]保证窗口内所有字符都是不重复的。2. 右指针 right 不断向右扩展每次将新字符 s[right]加入窗口。3. 如果 s[right] 在窗口内已经出现过(即其上次出现位置 left):→将1eft 移动到该字符上次出现位置的下一个位置从而消除重复。4. 每次移动后更新当前窗口长度并记录全局最大值。5. 最终返回全局最大值。【为什么用Map而不是 Set】- Map 存储每个字符的最新索引遇到重复时可以0(1)定位到重复位置从而让 left 直接跳跃比 Set while 循环更高效。【时间复杂度】0(n)每个字符最多被1eft 和right各访问一次整体线性。【空间复杂度】O(min(n字符集大小))Map中最多存储字符集大小的条目对于ASCII字符集上限为128/256。);function lengthOfLongestSubstring(s: string): number { let left 0 let maxLength 0 const map new Mapstring,number() for(let right0;rights.length;right){ const cur s[right] if(map.has(cur)){ left Math.max(left,map.get(cur) 1) } map.set(cur,right) maxLength Math.max(maxLength,right-left1) } return maxLength };共勉