IT 面试题库

编程题:求「无重复字符的最长子串」长度(LeetCode 3),请用滑动窗口实现并说明复杂度。

中级编程题算法工程师Java后端工程师滑动窗口无重复子串哈希LeetCode3

题目

考察点:滑动窗口 + 哈希/数组记录字符最后出现位置;窗口收缩条件;为什么是 O(n) 而非 O(n^2);边界处理。属编程题。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 79 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:

  def lengthOfLongestSubstring(s):
      last = {}
      left = 0
      best = 0
      for right, ch in enumerate(s):
          if ch in last and last[ch] >= left:
              left = last[ch] + 1
          last[ch] = right
          best = max(best, right - left + 1)
      return best
  
练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题