LeetCode每日一练（无重复字符的最长子串）

梦里梦外; 2022-10-20 00:55 54阅读 0赞

题目如下：

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

![在这里插入图片描述][20210712130232866.png]  
题目要求找出给定字符串中不含重复字符的最长子串，我们可以采用暴力穷举的方式，得到字符串中的所有子串，然后一一判断不重复子串的长度，最后返回最长子串的长度即可，比如：  
![在这里插入图片描述][20210712131539210.png]  
对于这样的一个字符串，我们首先从头开始进行遍历，将a取出：  
![在这里插入图片描述][2021071213172293.png]  
然后取出下一个字符b，查看该字符是否重复，若不重复，继续放入新的字符串中：  
![在这里插入图片描述][20210712131802301.png]  
下一个字符c也是如此：  
![在这里插入图片描述][20210712131818658.png]  
紧接着下一个字符是a，此时发现新字符串中已经有了字符a，发生了重复，所以现在记录一下新字符串的长度，为3，然后从原字符串的第二个字符开始继续进行遍历：  
![在这里插入图片描述][2021071213204349.png]  
再看下一个字符c，仍然放入新字符串：  
![在这里插入图片描述][20210712132112846.png]  
直至遇到字符b，又产生了重复：  
![在这里插入图片描述][2021071213221551.png]  
此时仍然记录当前新字符串的长度，并从原字符串的第三个字符开始遍历：  
![在这里插入图片描述][20210712132237476.png]  
以此类推，就得到了一个无重复字符子串的长度表：  
![在这里插入图片描述][20210712132423684.png]  
此时只需取出长度表中的最大值，即为字符串中无重复字符的最长子串长度。

清楚了算法思想之后，就可以写出代码：

public static int lengthOfLongestSubstring(String s) { 
            // 使用List集合来判断字符是否重复出现
            List<Character> list = new ArrayList<>();
            // 存储所有无重复子串的长度
            List<Integer> lenList = new ArrayList<>();
            // 记录子串长度
            int count = 0;
            char[] charArray = s.toCharArray();
            // 穷举所有子串
            for (int i = 0; i < charArray.length; ++i) { 
                for (int j = i; j < charArray.length; ++j) { 
                    // 判断字符是否重复出现
                    if (list.contains(charArray[j])) { 
                        // 若出现，则记录当前子串的长度
                        lenList.add(count);
                        // 集合清空，count归0
                        list.clear();
                        count = 0;
                        // 结束本次循环
                        break;
                    } else { 
                        // 若未出现，则添加
                        list.add(charArray[j]);
                        count++;
                    }
                }
            }
            // 对存放无重复子串长度的集合进行由大到小的排序
            lenList.sort((o1, o2) -> o2 - o1);
            // 排序后的首个元素即为集合中的最大值
            return lenList.get(0);
        }

将代码进行提交，结果出错：  
![在这里插入图片描述][20210712132702217.png]  
原来我们没有考虑什么都不输入的情况，若无输入，则直接返回长度0即可，对于长度为1的输入，我们也得单独考虑，因为刚才的程序只有在出现重复字符的时候才会记录当前子串的长度，而如果输入字符串的长度为1，就没有重复的情况了，所以单独处理这两种情况即可，修改代码：

public static int lengthOfLongestSubstring(String s) { 
            // 若字符串长度为1，则直接返回1
            if (s.length() == 1) { 
                return 1;
            }
            // 若无输入，则直接返回0
            if (s.length() == 0) { 
                return 0;
            }
            // 使用List集合来判断字符是否重复出现
            List<Character> list = new ArrayList<>();
            // 存储所有无重复子串的长度
            List<Integer> lenList = new ArrayList<>();
            // 记录子串长度
            int count = 0;
            char[] charArray = s.toCharArray();
            for (int i = 0; i < charArray.length; ++i) { 
                for (int j = i; j < charArray.length; ++j) { 
                    // 判断字符是否重复出现
                    if (list.contains(charArray[j])) { 
                        // 若出现，则记录当前子串的长度
                        lenList.add(count);
                        // 集合清空，count归0
                        list.clear();
                        count = 0;
                        // 结束本次循环
                        break;
                    } else { 
                        // 若未出现，则添加
                        list.add(charArray[j]);
                        count++;
                    }
                }
            }
            // 对存放无重复子串长度的集合进行由大到小的排序
            lenList.sort((o1, o2) -> o2 - o1);
            // 排序后的首个元素即为集合中的最大值
            return lenList.get(0);
        }

测试通过：  
![在这里插入图片描述][20210712133033297.png]  
暴力穷举虽然解决了题目需求，但执行效率非常低，为此，这里再介绍另外一种解决方案：滑动窗口。

对于这样的一个字符串：  
![在这里插入图片描述][20210712135127683.png]  
我们设置一个滑动窗口，该窗口内的子串就是无重复字符的最长子串，定义两个指针用于划分窗口的左边界和右边界，并指定此时最长子串长度为1：  
![在这里插入图片描述][20210712135458810.png]  
让right指针右移，扩大滑动窗口范围，此时最长子串长度为2：  
![在这里插入图片描述][20210712135544485.png]  
继续右移right指针，最长子串长度为3：  
![在这里插入图片描述][20210712135613805.png]  
当再次右移right指针时，发现字符a已经在滑动窗口中出现：  
![在这里插入图片描述][20210712135824168.png]  
此时我们需要缩小滑动窗口，使其不再与当前字符a重复，让left指针右移：  
![在这里插入图片描述][20210712135914806.png]  
当滑动窗口已不再与字符a重复后，扩大滑动窗口，right右移，此时最长子串长度仍为3：  
![在这里插入图片描述][20210712140044523.png]  
此时又发现字符b与窗口中的字符重复，继续缩小滑动窗口：  
![在这里插入图片描述][20210712140147228.png]  
无重复后，扩大滑动窗口，right指针右移：  
![在这里插入图片描述][20210712140301665.png]  
以此类推，直到遍历结束。

代码如下：

public static int lengthOfLongestSubstring(String s) { 
            // 若无输入，则直接返回0
            if (s.length() == 0) { 
                return 0;
            }
            // 定义滑动窗口左边界
            int left = 0;
            // 定义滑动窗口右边界
            int right = 0;
            // 无重复子串的最大长度
            int maxLen = 1;
            // 模拟滑动窗口
            Set<Character> set = new HashSet<>();
            // 遍历字符串
            while(right < s.length()){ 
                // 若滑动窗口中的字符与当前字符重复，则缩小滑动窗口，直至无重复为止
                while (set.contains(s.charAt(right))) { 
                    set.remove(s.charAt(left));
                    left++;
                }
                // 计算当前滑动窗口长度，并与maxLen比较，取最大值作为新的无重复子串长度
                maxLen = Math.max(maxLen, right - left + 1);
                // 扩大滑动窗口
                set.add(s.charAt(right));
                right++;
            }
            return maxLen;
        }

测试通过：  
![在这里插入图片描述][20210712140744931.png]  
该算法仍然有可以改进的地方，比如：  
![在这里插入图片描述][20210712141103357.png]  
对于这样的一个字符串，当滑动窗口遇到重复字符：  
![在这里插入图片描述][20210712141146508.png]  
此时缩小滑动窗口，left要一直右移，直至将字符w删除：  
![在这里插入图片描述][20210712141355935.png]  
那么有没有办法能够让left直接移动到重复字符的下一个字符呢？我们可以改用HashMap来模拟滑动窗口，因为HashMap可以存储一个值，我们就让它存储字符的索引即可。  
所以当遇到重复字符w时，直接从HashMap中取出滑动窗口中w的索引3，然后直接让left指针跳转至下一个索引4的位置即可。

代码如下：

public static int lengthOfLongestSubstring(String s) { 
            // 若无输入，则直接返回0
            if (s.length() == 0) { 
                return 0;
            }
            // 定义滑动窗口左边界
            int left = 0;
            // 定义滑动窗口右边界
            int right = 0;
            // 无重复子串的最大长度
            int maxLen = 1;
            // 模拟滑动窗口
            Map<Character, Integer> map = new HashMap<>();
            // 遍历字符串
            while (right < s.length()) { 
                // 若滑动窗口中的字符与当前字符重复，则缩小滑动窗口
                int index = map.getOrDefault(s.charAt(right), -1);
                // 直接让left指针跳转至滑动窗口中重复字符的下一个字符
                left = Math.max(left, index + 1);
                // 计算当前滑动窗口长度，并与maxLen比较，取最大值作为新的无重复子串长度
                maxLen = Math.max(maxLen, right - left + 1);
                // 扩大滑动窗口
                map.put(s.charAt(right), right);
                right++;
            }
            return maxLen;
        }

[20210712130232866.png]: /images/20221004/4210acb9ce0d45849cb68b1722c600a1.png
[20210712131539210.png]: /images/20221004/301adf0de581485e8b85f28107a187e6.png
[2021071213172293.png]: /images/20221004/b893f489e1fb4cb29274f7e6b2bf30a9.png
[20210712131802301.png]: /images/20221004/f174494e1a5d45ef8e7a70f907b7b116.png
[20210712131818658.png]: /images/20221004/16224a6dd75d44859379efdc17c92288.png
[2021071213204349.png]: /images/20221004/e6a9964dfe4a49719a80535ca7ec5d4d.png
[20210712132112846.png]: /images/20221004/3987678ae00947e48a393175e19f0f43.png
[2021071213221551.png]: /images/20221004/9baafa92fa064a159771d688c03986fc.png
[20210712132237476.png]: /images/20221004/5790d4e42b134837b652490a6bdc8a05.png
[20210712132423684.png]: /images/20221004/cd9c18ffc6c24c6495476155d2228052.png
[20210712132702217.png]: /images/20221004/6153173b7e2249bf9565558ace31a9c2.png
[20210712133033297.png]: /images/20221004/79f2081818e34493890cb8c0a69a9f5d.png
[20210712135127683.png]: /images/20221004/cf83953b33204869b3ebf01da4e64b45.png
[20210712135458810.png]: /images/20221004/6ce604bbd9e34d3ab225e20308395b7e.png
[20210712135544485.png]: /images/20221004/38651bc16ee444d889061c2268156e44.png
[20210712135613805.png]: /images/20221004/a1dc248b5c484a9985e144374d415da6.png
[20210712135824168.png]: /images/20221004/0682d6525aea4f249314b14f258072f0.png
[20210712135914806.png]: /images/20221004/61dfe21079b843fbaa2cf499e2dece96.png
[20210712140044523.png]: /images/20221004/972a6468fa254bec9021861495123ac8.png
[20210712140147228.png]: /images/20221004/e54d91e84c2f46e593e0cfe6ea2e4d61.png
[20210712140301665.png]: /images/20221004/527c8ee2d3a340918949f03dd817f1e4.png
[20210712140744931.png]: /images/20221004/a1a6b2f4ef7b48dda3c849f772a1fac7.png
[20210712141103357.png]: /images/20221004/5fec399fe65b4c1f986cbe5e43127a4a.png
[20210712141146508.png]: /images/20221004/a798b47cb305424b847ac6c30495f92e.png
[20210712141355935.png]: /images/20221004/91506d9d04a24bcab6c04da097e6e7c7.png