专栏首页InvQ的专栏用【滑动窗口】 比较长度,用 Hash Table 记录位置

用【滑动窗口】 比较长度,用 Hash Table 记录位置

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2:

输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示例 3:

输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。 请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。 示例 4:

输入: s = “” 输出: 0

提示:

0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

滑动窗口
暴力解法时间复杂度较高,会达到 O(n^2)O(n2),故而采取滑动窗口的方法降低时间复杂度
定义一个 map 数据结构存储 (k, v),其中 key 值为字符,value 值为字符位置 +1,加 1 表示从字符位置后一个才开始不重复
我们定义不重复子串的开始位置为 start,结束位置为 end
随着 end 不断遍历向后,会遇到与 [start, end] 区间内字符相同的情况,此时将字符作为 key 值,获取其 value 值,并更新 start,此时 [start, end] 区间内不存在重复字符
无论是否更新 start,都会更新其 map 数据结构和结果 ans。
时间复杂度:O(n)O(n)
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 报错 解决-bash: fork: retry: Resource temporarily unavailable

    在curl 一个 spring boot 应用接口的时候,出现这个情况,看着启动ok,但是出现如下提示

    MickyInvQ
  • 解决 Maven 使用Tomcat 部署报错 Tomcat return http status error: 405, Reason Phrase: Method Not Allowed:

    出现如下报错: Tomcat return http status error: 405, Reason Phrase: Method Not Allowe...

    MickyInvQ
  • XML 文档定义有几种形式?它们之间有何本质区别?解析 XML 文档有哪几 种方式?

    2)本质区别:schema 本身是 xml 的,可以被 XML 解析器解析(这也是从 DTD

    MickyInvQ
  • 画解算法 3-无重复字符的最长子串

    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

    灵魂画师牧码
  • 557. 反转字符串中的单词 III

    给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

    韩旭051
  • Go语言学习(四)| 数组、切片、集合

    array由 [n]<type> 定义,n为array的长度,<type>标示希望存储的内容的类型。例:

    Mervyn
  • 关于在Windows下AndroidStudio.使用React-Native开发android报错红屏“run react-native start”解决

    以下是报错,不过他已经给了解决办法,报错提示的大概中文译为“无法加载脚本,请确保你的Metro服务以及那个包正确”,由于我个人并不是专业安卓,公司项目没办法就上...

    公众号 碧油鸡
  • 微信小程序 nginx https 反向代理后端服务

    张琳兮
  • 微信小程序 nginx https 反向代理后端服务

    张琳兮
  • 轻松学会 React 钩子:以 useEffect() 为例

    但是,最近我逐渐体会到 React 钩子(hooks)非常好用,重新认识了 React 这个框架,觉得应该补上关于钩子的部分。

    ruanyf

扫码关注云+社区

领取腾讯云代金券