力扣热门100题——无重复字符的最长最长子串（滑动窗口，暴力循环，动态规划，同向双指针，byte数组）

2、无重复字符的最长子串

1.问题描述

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

2.示例

示例 1:

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

示例 2:

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

示例 3:

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

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

3.提示

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

4.具体解法（滑动窗口，暴力循环，动态规划，同向双指针，byte数组）

下面的是我自己的解题过程，最后的效果是只有一个超时的

解决办法知道是通过改进第二层的循环，但还不会写

//第一个想法就是暴力遍历
//从字符串的第一个字符开始依次往后遍历，可以用哈希表来存储，用一个变量存储最大值，一个变量存储临时的最大值
//可以用containsKey的方式判断是不是有重复了，也可以直接用set，add失败会自动返回false的
//问题是失败了之后，怎么重新开始用这个哈希表进行判断，因为里面已经存储了一些值了，我们要的是重新一个空的哈希表来进行新的判断
//所以我想是不是可以找到一个函数是可以清空哈希表的，真的有，就是clear()方法，可以清空表中所有键值对

//如何去遍历字符串呢
//学到了三种遍历方式，而且绝对还有更多，先学会一种比较好的，其他的慢慢接触
/*
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set chr=new HashSet<>();
        char[]  c = s.toCharArray();
        int max=0;//最后要输出的最大值
        int maxnow=0;//临时的最大值
        for(int i=0;i < c.length;i++){
            if(chr.add(c[i])){
                maxnow++;//只要能成功添加就最大值加一
            }
            else{
                chr.clear();//填不进去就重新清空开始计算
                if(max chr=new HashSet<>();
        char[]  c = s.toCharArray();
        int max=0;
        int maxnow=0;
        for(int i=0;i < c.length;i++){
            if(chr.add(c[i])){
                maxnow++;
            }
            else{
                chr.clear();
                chr.add(c[i]);
                if(maxmax){
            max=maxnow;
        }
        return max;

    }
}
 */
//改完之后反而更少了
//"pwwkew"我输出2，但是预期结果应该是3
//反思后发现了问题，在更新计数器这里，因为是我们把那个丢掉的补回去了，所以不应该是maxnow=0;，而应该是maxnow=1;


//再次修改之后，可以通过接近一半了
//"dvdf"我输出2，但是预期结果应该是3
//发现确实，这个是因为我没有进行二层循环的原因，本来一开始想到就是二层循环，写着写着给忘了

//写了二层循环，还是不行
//"asjrgapa"输出5，预期6
//发现是因为我会有一个重复之后添加进集合的 *** 作，这样导致第一层循环的时候有个a最后进了集合
//然后到二层循环的时候，一开始是a，然后重复，又重新开始计算，同时呢，a又进来了，所以会导致本来应该是sjrgap，变成了遇到a就停止了
//所以之前的aab，不应该用那个方式处理，而是二层循环就可以


//又出现问题了
//"jbpnbwwd"预期是4，我输出是5
//仔细想想应该是我每层循环结束没清零
//应该在每层循环结束的时候更新max，并且清空set集合，还得把计数器也同时清零


//终于又是遇到了超出时间限制了
//看评论有哥们提到第二层循环有重复的，的确想到之前的题目有遍历的情况，也是对二层循环进行了优化
//附上我最接近成功的版本
/*
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set chr=new HashSet<>();
        char[]  c = s.toCharArray();
        int max=0;
        int maxnow=0;
        for(int i=0;i < c.length;i++){
            for(int j=i;jmax){
                max=maxnow;
            }
            chr.clear();
            maxnow=0;
        }
        if(maxnow>max){
            max=maxnow;
        }
        return max;

    }
}
 */

下面的部分是比较成熟的代码

//方法一：滑动窗口
//假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 r_k
//那么当我们选择第 k+1个字符作为起始位置时，首先从 k+1 到 r_k的字符显然是不重复的
//并且由于少了原本的第 k 个字符，我们可以尝试继续增大 r_k直到右侧出现了重复字符为止。


//这样一来，我们就可以使用「滑动窗口」来解决这个问题了

//我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 r_k
//在每一步的 *** 作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，
//然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。


//在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。

我们记录下这个子串的长度；
//在枚举结束后，我们找到的最长的子串的长度即为答案。



//判断重复字符我们用HashSet
//在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。



//我的理解是，当我们已经左右指针有一点距离了，然后出现重复字符的时候，并不是像我们之前那样的处理方式，
//而是去掉左边第一个结点，同时右结点在我们当前的基础上继续往后，这样只需要一次遍历就可以实现我们的需求
//他的原理就好像我前面已经扩张的很大了，我没必要再从小开始扩张
//发现重复不是只移除一个元素，而是左指针一直右移删除，直到set内没有重复
/*
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;
    }
}
 */

//方法二：动态规划
//动态规划，dp[i]代表以i结尾的不重复子字符串的最大长度， 那么，对于i，有两种情况：

        //s[i]在子字符串s[i-1 - dp[i-1], i-1]中且重复索引为j, dp[i] = i-j;
        //s[i]在不子字符串s[i-1 - dp[i-1], i-1]中且重复索引为j, dp[i] =dp[i-1] + 1;

/*
int lengthOfLongestSubstring(string s) {
        int length = s.length();
        if(length == 0) return 0;
        int dp[length];
        int ans = 1;
        dp[0] = 1;
        for(int i=1;i= i)
        dp[i] = dp[i-1] + 1;
        else if(res < i )
        dp[i] = i-res;
        ans = max(ans, dp[i]);
        }
        return ans;
        }
 */

//方法三：暴力循环
//并没有感觉这种暴力的方式比我会强到哪里呢，为什么我会超时
/*
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        if (s == null || s == "") {
            return result;
        }
        Map substring = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            substring.clear();
            Character left = s.charAt(i);
            substring.put(left, left);
            int len = 1;
            for (int j = i + 1; j < s.length(); j++) {
                // [i, j]就是子串
                Character right = s.charAt(j);
                if (substring.containsKey(right)) {
                    break;
                } else {
                    len++;
                    substring.put(right, right);
                }
            }
            result = Math.max(result, len);
        }
        return result;
    }
}
 */
//方法四：同向双指针
//这题可以用同向双指针来解，[left, right]都 从头向尾遍历，双指针所指向 的子串就是符合题意的子串，即无无重复的子串。


//右指针可以每次向后移动1个，当新字符与子串中无重复时继续向右移动right
//但当有重复字符时，把左指针left移动到子串中重复字符的下一个（注意这一步是跟滑动窗口不同的）
//这样移动后的[left, rihgt]中依然是无重复字符的子串。

直到把整个字串遍历完成。


//但是它的效率是最差的
/*
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        if (s == null || s == "") {
            return result;
        }
        Map substring = new HashMap<>();
        int i = 0;
        while (i < s.length()) {
            substring.clear();
            substring.put(s.charAt(i), i);
            int len = 1;
            int j = i + 1;
            while (j < s.length()) {
                Character right = s.charAt(j);
                if (substring.containsKey(right)) {
                    break;
                }
                substring.put(right, j);
                len++;
                j++;
            }

            result = Math.max(result, len);

            if (j == s.length()) {
                // we are done
                break;
            }
            i = substring.get(s.charAt(j)) + 1;
        }
        return result;
    }
}
 */
//方法五：用byte数组替代哈希表
//字符串是一个有限集合，题目说了是ASCII，最多就是128个字符，并且字符是无符号short，可以作为数组下标。


//无重复子串，也就是说子串中每个字符最多出现1次，且出现2次时就需要去重。


// 由此，完全 没有必要用哈希表，因为哈希表只是理论上是O(1)的，且有自动装箱/拆箱，实际运行效率较差。


//ASCII字符最多128个，数量最多不超2,所以这里完全 可以用一个长度为128的byte数组作代替哈希表。


//这是最优解
/*
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        if (s == null || s == "") {
            return result;
        }
        byte[] substring = new byte[128];
        int i = 0;
        for (int j = 0; j < s.length(); j++) {
            substring[s.charAt(j)] += 1;
            while (i < j && substring[s.charAt(j)] != 1) {
                substring[s.charAt(i)] -= 1;
                i++;
            }
            result = Math.max(result, j - i + 1);
        }

        return result;
    }
}
 */

5.收获

• 复习并掌握了字符串的遍历，十分建议大家对常见数据类型和数据结构都掌握各自的遍历方式，后面我也要整理一下，字符串的几种遍历方式具体可以看另一篇文章https://blog.csdn.net/humor2020/article/details/123898983?spm=1001.2014.3001.5501

• 其实这个时候才逐渐感觉到那些培训机构的课为什么很多时候讲各种遍历，因为很多题目都离不开对各种类型的遍历，有时间需要去几种整理一下

• 几个问题

  • 基础知识基本忘得一干二净，常用的API函数也记不清楚了，得现查
  • 除了暴力法，其他的思路几乎没有，只会结合点哈希表的方式
  • 考虑问题不够全面，急急忙忙得就开始写代码了，最后导致的结果就是。
    

    
    

    。
    

    
    

    填坑

• 在分析问题的时候，注意null啊这种情况，也是要考虑进来的

• 自己写的循环总是出现时间超出的情况，还是要想办法成功一次，但是看别人的暴力循环并没有比我的强到哪里去，为什么会呢，可能是里面的遍历，哈希表等结构拥有不同的特点和时间吧

• 学习到了滑动窗口的概念和使用