【今日最佳leecode】无重复字符的最长子串

2020-11-30 本文已影响0人 rs汀

img

相信看了这个标题的同学，对这道题以已经非常不陌生了，就是leecode当中的第三题，之所以要单独的写一写主要对我来说，里面涉及到有一个滑动窗口, 散列表，字符编码等知识点比较重要，也有几个小技巧，这里我也权当记忆巩固了，这道题也曾被Micosoft, Amazon, Bloomberg, Airbnb, Adobe作为经典面试题，包括限流, TCP拥塞都有使用到滑动窗口思想。

题目

给给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: "abcabcbb"

输出: 3

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

输入: "pwwkew"

输出: 3

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

举例：

img

作为大多数人，找出如图的不相同字符的最大长度，基本上判断3次，ABC长度为3，BCAD长度为4，CADC长度为3，判断到这里直接就可以给出答案了，就是4，因为CADC已经到字符串末尾了，不用再比较了。但是让程序去实现这个功能就要设计一下了。

根据事例提出几个问题：

①在第一轮判定了ABC都不重复，我们怎么实现将BC作为一个整体第二轮就不需要要判断BC是不重复的子串?

②如何选取数据结构？

<font face="黑体">滑动窗口：</font>

顾名思义，滑动窗口通常指可以动态扩容和缩容的一个窗口，如"ABCADC“这个事例，在第二轮我们视BC为一个整体进行扩容，扩容到BCAD。

img

如”pwwkew“，在第二轮当PW遇到W，我们进行缩容，直接从下一个W开始。如图所示。通常滑动窗口的实现需要结合散列表来实现来维护一个不重复子串，当获取接下来的字符如果存在在散列表中，指针右移。

img

散列表：

通常一旦涉及到出现次数，我们可以用散列表，在Java中我们常用的涉及到散列表的容器有HashMap， HashSet, HashTable等等。这里我们可以选用HashSet,其实其它几种都可以实现。

Set<Character> occ = new HashSet<>(); // 创建一个散列表
occ.remove(s.charAt(i - 1));          // 指针右移(移除）
occ.add((s.charAt(rk + 1)));          // 指针右移(添加)
!occ.contains(s.charAt(rk + 1))       // 判断接下来的字符是否出现在散列表

参考代码

public static int lengthOfLongestSubstring(String s) {
    // 哈希集合，记录每个字符是否出现过
    Set<Character> 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));
        }
        if (ans >= n -i) {
            break;
        }
        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;
}

测试用例：

@Test
public void islengthOfLongestSubstring() {
//  int i = lengthOfLongestSubstring("abcadc");
    int i = lengthOfLongestSubstring("pwwkew");
    Assert.assertNotNull(i);
}

拓展

public int lengthOfLongestSubstring1(String s) {
        if(s==null||s.equals(""))
            return 0;
        int []map = new int[256];
        for(int i=0;i<256;i++)
            map[i]=-1;
        int len = 0, cur = 0, pre = -1;
        for(int i=0;i<s.length();i++){
            int x = s.charAt(i);
            pre = Math.max(pre,map[x]); // 记录上次比较出现过得最大值
            cur = i - pre; // 指针 - 最大值,当指针右移，i变大，他们的差值就越大;出现相同的值，pre变大
            len = Math.max(len,cur);
            map[x] = i;  // 对出现过的字符赋值为字符串下标
        }
        return len;
    }

我们知道，在计算机中，所有的数据在存储和运算时都要使用二进制数表示，在英语中，用128个符号编码便可以表示所有，其他语言，128个符号是不够的。一些欧洲国家决定，利用字节中闲置的最高位编入新的符号，这些欧洲国家使用的编码体系，可以表示最多256个符号。但是汉字多达10万左右，汉字使用GB2312，理论上可以表示 256 x 256 = 65536 个符号。

在本题中主要只涉及到字符串，完全可以使用一个数组，容量大小是256，初始长度都为-1，出现过的值记录一下，pre比较出现过的值，通过右移指针与pre的差来记录最近一次最大值，len为历史最大值。

热门推荐：

文末福利，最近整理一份面试资料《Java面试通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式：GitHub github.com/Tingyu-Notes，更多内容关注我的简书，陆续奉上。

【今日最佳leecode】无重复字符的最长子串

猜你喜欢

热点阅读