003. 无重复字符的最长子串 | Leetcode题解

苏南

发布于 2020-12-16 14:41:07

5250

发布于 2020-12-16 14:41:07

文章被收录于专栏：漫画前端

点击上方“蓝色字体”，选择“设为星标”

每天复习一道面试题，轻松拿大厂Offer~

题目描述

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

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

难度：

难度：中等
支持语言：JavaScript、Java、Python、C++

思路

题目要求连续，我们考虑使用滑动窗口。而这道题就是窗口大小不固定的滑动窗口题目，然后让我们求满足条件的窗口大小的最大值，这是一种非常常见的滑动窗口题目。

算法：

用一个 hashmap 来建立字符和其出现位置之间的映射。同时维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

如果当前遍历到的字符从未出现过，那么直接扩大右边界；
如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
重复（1）（2），直到窗口内无重复元素；
维护一个全局最大窗口 res，每次用出现过的窗口大小来更新结果 res，最后返回 res 获取结果;
最后返回 res 即可;

(图片来源：https://github.com/MisterBooo/LeetCodeAnimation)

维护数组：

使用一个数组来维护滑动窗口，遍历字符串，判断字符是否在滑动窗口数组里

不在则 push 进数组
在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
然后将 max 更新为当前最长子串的长度
遍历完，返回 max 即可

滑动窗口暴力解法：

暴力解法时间复杂度较高，会达到 O(n^2)O(n 2)，故而采取滑动窗口的方法降低时间复杂度
定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复
我们定义不重复子串的开始位置为 start，结束位置为 end
随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符
无论是否更新 start，都会更新其 map 数据结构和结果 ans。

关键点

mapper 记录出现过并且没有被删除的字符
滑动窗口记录当前 index 开始的最大的不重复的字符序列

复杂度分析

时间复杂度：
空间复杂度：

代码

JavaScript 实现

/**
*  @作者：user7746o
*  @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/zi-jie-leetcode3wu-zhong-fu-zi-fu-de-zui-chang-zi-/
*/
var lengthOfLongestSubstring = function(s) {
    let arr = [], max = 0
    for(let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if(index !== -1) {
            arr.splice(0, index+1);
        }
        arr.push(s.charAt(i))
        max = Math.max(arr.length, max)
    }
    return max
};

/**
*  @作者：Heternally
*  @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javascriptjie-fa-chao-9998-by-heternally/
*/
var lengthOfLongestSubstring = function(s) {
  let num = 0,res = 0;
  let m = '';
  for (n of s) {
    if (m.indexOf(n) == -1) {
      m += n;
      num++;
      res = res < num ? num: res;
    } else {
      m += n;
      m = m.slice(m.indexOf(n)+1);
      num = m.length;
    }
  }
  return res;
};

C++ 实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int ans = 0, start = 0;
        int n = s.length();
        //
        map<char, int> mp;

        for(int i=0;i<n;i++)
        {
            char alpha = s[i];
            if(mp.count(alpha))
            {
                start = max(start, mp[alpha]+1);
            }
            ans = max(ans, i-start+1);
            // 字符位置
            mp[alpha] = i;
        }

        return ans;
    }
};

/**
*  @作者：LeetCode-Solution
*  @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合，记录每个字符是否出现过
        unordered_set<char> occ;
        int n = s.size();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        // 枚举左指针的位置，初始值隐性地表示为 -1
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
                // 不断地移动右指针
                occ.insert(s[rk + 1]);
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

/**
*  @作者：pinku-2
*  @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-cshi-xian-/
*/
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        //s[start,end) 前面包含 后面不包含
        int start(0), end(0), length(0), result(0);
        int sSize = int(s.size());
        while (end < sSize)
        {
            char tmpChar = s[end];
            for (int index = start; index < end; index++)
            {
                if (tmpChar == s[index])
                {
                    start = index + 1;
                    length = end - start;
                    break;
                }
            }

            end++;
            length++;
            result = max(result, length);
        }
        return result;
    }
};

Java 实现

思路：
暴力解法时间复杂度较高，会达到 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 ans = 0, start = 0;
        int n = s.length();
        //
        Map<Character, Integer> map = new HashMap<>();

        for(int i=0;i<n;i++)
        {
            char alpha = s.charAt(i);
            if(map.containsKey(alpha))
            {
                start = Math.max(start, map.get(alpha)+1);
            }
            ans = Math.max(ans, i-start+1);
            // 字符位置
            map.put(alpha, i);
        }

        return ans;
    }
}

/**
*  @作者：guanpengchn
*  @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/
*/
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;
    }
}

/**
*  @作者：VioletKiss
*  @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javati-jie-3wu-zhong-fu-zi-fu-de-zui-chang-zi-chua/
*/

class Solution {
 public int lengthOfLongestSubstring(String s) {
  int i = 0;
  int flag = 0;
  int length = 0;
  int result = 0;
  while (i < s.length()) {
   int pos = s.indexOf(s.charAt(i),flag);
   if (pos < i) {
    if (length > result) {
     result = length;
    }
    if (result >= s.length() - pos - 1) {
     return result;
    }
    length = i - pos - 1;
    flag = pos + 1;
   }
   length++;
   i++;
  }
  return length;
 }
}

Python3 实现

from collections import defaultdict


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        ans = 0
        counter = defaultdict(lambda: 0)

        for r in range(len(s)):
            while counter.get(s[r], 0) != 0:
                counter[s[l]] = counter.get(s[l], 0) - 1
                l += 1
            counter[s[r]] += 1
            ans = max(ans, r - l + 1)

        return ans


# @作者：powcai
# @链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len


# @作者：marcusxu
# @链接：链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/python3ti-jie-chao-jian-dan-de-dong-tai-gui-hua-ji/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == '':
            return 0
        if len(s) == 1:
            return 1

        def find_left(s, i):
            tmp_str = s[i]
            j = i - 1
            while j >= 0 and s[j] not in tmp_str:
                tmp_str += s[j]
                j -= 1
            return len(tmp_str)
        length = 0
        for i in range(0, len(s)):
            length = max(length, find_left(s, i))
        return length

其他

原题leetcode链接：3.longest-substring-without-repeating-characters
合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
说明：leetcode 题解 | 每日一题? 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。

- 完 -

关注公众号「IT平头哥联盟」，一起进步，一起成长！

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-11，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

javascript

编程算法

本文分享自画漫画的程序员微信公众号，前往查看

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

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据结构

javascript

编程算法

登录后参与评论

0 条评论

热度

003. 无重复字符的最长子串 | Leetcode题解

003. 无重复字符的最长子串 | Leetcode题解

题目描述

难度：

相关标签

相关企业

思路

算法：

维护数组：

滑动窗口暴力解法：

关键点

复杂度分析

代码

JavaScript 实现

C++ 实现

Java 实现

Python3 实现

其他

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

003. 无重复字符的最长子串 | Leetcode题解

003. 无重复字符的最长子串 | Leetcode题解

题目描述

难度：

相关标签

相关企业

思路

算法：

维护数组：

滑动窗口 暴力解法：

关键点

复杂度分析

代码

JavaScript 实现

C++ 实现

Java 实现

Python3 实现

其他

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

滑动窗口暴力解法：