【LeetCode】003：无重复字符的最长子串-白红宇

【LeetCode】003：无重复字符的最长子串

阅读量：2054 次

发布时间：2019-04-28

本文共 2076 字，大约阅读时间需要 6 分钟。

记录一下自己的练习。

题目

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

示例

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

方法

01 使用hashmap

解题思路

用 哈希表 存储字符串，key是字符串中每个字符，value是字符最后出现的下标；

使用一个指针start，表示不重复子串的开始下标；

遍历字符串中每个字符，如果当前字符【下标为 i 】在哈希表中已经存在，且下标大于start，则说明 [start,i-1] 是一个不含有重复字符的子串，更新start值。

在这里插入图片描述

代码

class Solution {
       public int lengthOfLongestSubstring(String s) {
            if(s == null || s.length() == 0) {
             	return 0;          }        // 最大字串长度        int result = 0;        // 子串开始下标        int start = 0;        // 存储最大字串        Map
   
     map = new HashMap<>();        for (int i = 0; i < s.length(); i++) {
               Integer index = map.get(s.charAt(i));            map.put(s.charAt(i),i);                        if(index != null && start <= index){
                   start = index + 1;            }            result = result >= (i - start + 1) ? result : (i - start + 1);        }        return  result >= (s.length() - start ) ? result : (s.length() - start);    }}

复杂度分析

时间复杂度： $O (N)$ ，其中 $N$ 是字符串的长度。
空间复杂度： $O (∣ Σ ∣)$ ，其中 $∣ Σ ∣$ 表示字符集的大小，map中只存字符最后出现的下标。

02 官方答案

class Solution {
       public int lengthOfLongestSubstring(String s) {
           // 哈希集合，记录每个字符是否出现过        Set
   
     occ = new HashSet
    
     ();        int n = s.length();        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动        int rk = -1, ans = 0;        for (int i = 0; i < n; ++i) {
               if (i != 0) {
                   // 左指针向右移动一格，移除一个字符                occ.remove(s.charAt(i - 1));            }            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                   // 不断地移动右指针                occ.add(s.charAt(rk + 1));                ++rk;            }            // 第 i 到 rk 个字符是一个极长的无重复字符子串            ans = Math.max(ans, rk - i + 1);        }        return ans;    }}

复杂度分析

时间复杂度： $O (N)$ ，其中 $N$ 是字符串的长度。
空间复杂度： $O (∣ Σ ∣)$ ，其中 $Σ$ 表示字符集（即字符串中可以出现的字符）， $∣ Σ ∣$ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 $[0, 128)$ 内的字符，即 $∣ Σ ∣ = 128$ 。