侧边栏壁纸
  • 累计撰写 416 篇文章
  • 累计创建 65 个标签
  • 累计收到 145 条评论

目 录CONTENT

文章目录

LeetCode 第三题,无重复字符的最长子串

Z同学
2022-01-19 / 0 评论 / 1 点赞 / 4,252 阅读 / 1,774 字
温馨提示:
本文最后更新于 2022-10-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1.题目

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

示例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 由英文字母、数字、符号和空格组成

2. 解题思路

结合题目要求和示例我们可以暂时汇总:

  1. 字符串长度可以为0。
  2. 要计算不重复的子串,同时比较谁最长。输出最长的值就可以了。
  3. 字符串里面有数字,字面和空格。

暴力破解方法就是拿当前字符和后面的字符一个一个比较,如果中间有重复的。我们就移动下一位继续比较。

然后将数值计算,判断谁大。

示例:

输入: s = "abcabcbb"
第一局:ab,abc,abca失败  长度为3
第二局:bc,bca,bcab失败 长度为3
第三局:ca,cab,cabc失败,长度为3
第四局:ab,abc,abcb失败,长度为3
第五局:bc,bcb失败,长度为2
第六局:cb,cbb 失败,长度为2
第七局:bb失败,长度为0

最大长度为:3

我们如果直线思维,通过字符串添加和移除的逻辑书写代码:

示例1:

    public int lengthOfLongestSubstring(String s) {
        int i = -1;//在字符串中的下标
        StringBuilder builder = new StringBuilder();
        int size=0;
        if (s.length() != 0) {
            for (char t : s.toCharArray()) {
                i = builder.indexOf(t + "");
                if (i != -1) {
                    builder.delete(0, i+1);
                }
                builder.append(t);
                if (size < builder.length()) {
                    size = builder.length();
                }
            }
        }
        return size;
    }

我们将字符串存到StringBuilder中,然后一点点判断是否有下标。如果有就从0到该位置的字符进行删除,然后再添加新的字符,进行比较。上面的代码理解很简单,但是执行速度和效率就不行了。

image-20220119115030805

花费了11毫秒,只击败了20.63%

结果出来了,但是效率并不满意。我们继续优化。

除了粗暴的字符串拼接,有没有更好的解决思路呢?官方提供了一个参考示例:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合,记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        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;
    }
}

使用哈希集合记录字符,然后移动哈希集合的左右指针位置。

image-20220119154018963

我们可以看到,内存占用没有太大变化,但是耗时得到了很大提升。

之后发现有大神出的更快版本,采用int 256来替换map。妙啊。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxSize = 0;
        int [] dict = new int[256]; //记录ASCII 码字符出现的位置,以字符作为下标
        int base = 0;
        int key = 0;
        int i=0;
        while(key < s.length()){
            i = s.charAt(key);
            if(dict[i] > base)
                base = dict[i];
            dict[i] = key+1; //以1作为起始位置,下标加1
            maxSize = (maxSize>key-base+1)?maxSize:key-base+1;
            key++;
        }
        return maxSize;
    }
}

image-20220119154522650

速度得到了完全的提升。下面详细介绍该方法的思路。

2.1 ASCII 字符方案详解

我们一行一行代码,来分析ASCII 字符解决方案为什么可以成功。

public int lengthOfLongestSubstring(String s) {
        int maxSize = 0; //用来存储最长的子串的长度。
    	//创建一个256位的Int对象。
        int [] dict = new int[256]; //记录ASCII 码字符出现的位置,以字符作为下标, 
        int base = 0;  // 当前指针计算的起始位置
        int key = 0; //指针位置,也就是当前比较的字符串的下标位置。
        int i=0;  //当前字符的ASCII值。
        while(key < s.length()){ //下标只要小于字符串长度,我们就继续循环
            //字符串可以直接转为Char[]。 我们通过下标获取当前的Char对象的int 也就是ASCCII码。
            i = s.charAt(key);   //例如a 的ASCII码为97。
            if(dict[i] > base)  // 检测当前数组该位置上是否有值,前面没有循环到的字符,该位置为0
                base = dict[i];  
            dict[i] = key+1; //以1作为起始位置,下标加1。
            maxSize = (maxSize>key-base+1)?maxSize:key-base+1; //判断新字符串长度有没有超过最大的,有就用新的,没有就还是保持最大值
            key++;  //下标加1 进入下一个循环。一直到字符串循环结束
        }
        return maxSize; //输出结果
    }

问题1: 为什么Int 的字符长度设置为256?

题目中说了,s 是由英文字母+数字+符号+空格组成。它们的ASCII值分别是:

0~31 和127 :为各种控制字符,例如换行,回车,删除,制表符,等

32:为空格。

48~57:为0到9十个阿拉伯数字。

65~90:为26个大写英文字母。

97~122:为26个小写英文字母。

之后的就是各种符号了,全部的值就是256种。所以我们int的数组长度要定义为256

否则会出现下标越界。

问题2:base值为什么是key+1?

因为每次给base赋值的时候,就代表当前出现了重复字段了。所以计算字符长度就要从key+1开始计算

问题3:dict[i] = key+1 为什么要+1呢?

因为,默认字符长度都是从1开始的。而循环中key是从0开始的。不加1的话,就短了。

而最终判断的maxSize 就是比较当前的位置-开始位置然后+1 得到的子字符串长度。

参考资料

题目来源于LeetCode :3. 无重复字符的最长子串 - 力扣(LeetCode) (leetcode-cn.com)

1

评论区