前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【剑指offer:最长不含重复字符的子字符串】滑动窗口(双指针)+优化改进思路

【剑指offer:最长不含重复字符的子字符串】滑动窗口(双指针)+优化改进思路

作者头像
心谭博客
发布2020-04-21 10:39:49
4340
发布2020-04-21 10:39:49
举报
文章被收录于专栏:YuanXinYuanXin

题目描述:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

题目分析

留意最长子串和子序列不是一个概念。例如对“pwwkew”来说,最长子串是“wke”,“pwke”是其中一个子序列。

在不考虑时间的情况下,直接暴力法对所有的子串进行检查。复杂度是$O(N^3)$,会超时错误。

解法 1: 滑动窗口

准备 2 个指针 i、j,i 指向窗口左边,j 指向右边。指针每次可以向前“滑动”一个位置,它们之间的区域就是“窗口”。

整体流程如下:

  1. 准备哈希表 map。key 是 char,value 是 boolean,代表字符 char 是否出现在滑动窗口内
  2. i 和 j 初始化为 0,结果 ans 初始化为 0
  3. 检查s[j]是否出现过:
    • 没有出现过,扩大窗口:记录s[j],指针 j 向右滑动一格,更新 ans
    • 出现过,缩小窗口:指针 i 向右移动一格,map[s[i]]更新为 false
  4. 如果 i 和 j 没有越界,回到 step3,否则返回 ans

代码实现如下:

代码语言:javascript
复制
// ac地址:https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
// 原文地址:https://xxoo521.com/2020-03-11-length-of-substring/

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const length = s.length;
    const map = {}; // char => boolean 代表着char是否在目前的窗口内
    let i = 0,
        j = 0;
    let ans = 0;
    while (i < length && j < length) {
        if (!map[s[j]]) {
            ans = Math.max(j - i + 1, ans);
            map[s[j]] = true;
            ++j;
        } else {
            // 如果char重复,那么缩小滑动窗口,并更新对应的map
            map[s[i]] = false;
            ++i;
        }
    }

    return ans;
};

由于整个过程就是“推着”滑动窗口从左到右,时间复杂度是$O(N)$,空间复杂度是$O(N)$。

解法 2: 优化后的滑动窗口

在解法 1 的流程中的第 3 步,如果s[j]出现在滑动窗口内,采用的做法是左边逐步缩小滑动窗口。事实上,不需要逐步缩小。假设滑动窗口内和s[j]相同字符下标是 j’,那么直接跳过[i, j'] 范围即可。

为了做到“跳动优化”,需要改造一下对哈希表 map 的用法:key 还是 char;value 变为 int,记录 char 对应的下标。

整体代码实现如下:

代码语言:javascript
复制
// ac地址:https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
// 原文地址:https://xxoo521.com/2020-03-11-length-of-substring/

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const length = s.length;
    const map = new Map();
    let i = 0,
        j = 0;
    let ans = 0;
    while (i < length && j < length) {
        // 容易理解:检查s[j]是否出现过,并且s[j]重复的字符是否在当前的滑动窗口中
        if (map.has(s[j]) && map.get(s[j]) >= i) {
            i = map.get(s[j]) + 1;
        }
        ans = Math.max(j - i + 1, ans);
        map.set(s[j], j);
        ++j;
    }
    return ans;
};

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-03-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目分析
  • 解法 1: 滑动窗口
  • 解法 2: 优化后的滑动窗口
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档