LeetCode—无重复字符的最长子串

小鱼儿 2022-04-08 10:12 227阅读 0赞

## LeetCode—无重复字符的最长子串 ##

题目：

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

*  示例１：

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

*  示例 2：

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

*  示例 3：

输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

--------------------

思路：这道题是**字符串类型**的算法题中比较典型的一种题了，但是我也才刚开始接触算法，所以思路也并不清晰．起初，我觉得可以暴力来做，就是：枚举出字符串的所有子串，并且判断其是不是无重复字符的，如果是，则记录其长度，并与标记值max比较，然后就可以得出结论．

我们来分析一下暴力法所消耗的时间吧，枚举子串：Ｏ(n ^ 2)，在加上子串出来后，可以遍历子串并使用HashSet检查是否有重复字符，这样双重循环里又是一个O(n)，所以总体的时间复杂度为O(n ^ 3)，这肯定是过不去的，在字符串较短的时候还能计算出来，一旦用例加长，就会超出时间限制.

下面是暴力法的代码

/**
         * 1.暴力法枚举处所有可能情况,并求解 (超出时间限制)
         * 时间复杂度:O(n^3)
         */
        public int violence(String s) {
            int length = s.length();
            int ans = 0;
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length + 1; j++) {
                    if (allUnique(s,i,j)) {
                        ans = Math.max(ans,j - i);
                    }
                }
            }
            return ans;
        }
    
        /**
         * 判断字符串中子串是否含有重复的字母
         */
        public boolean allUnique(String s, int start, int end) {
            Set<Character> set = new HashSet<>();
            for (int i = start; i < end; i++) {
                Character ch = s.charAt(i);
                if (set.contains(ch)) {
                    return false;
                }
                set.add(ch);
            }
            return true;
        }

仔细一想感觉很没必要啊，因为：很多子串我们是不需要的，比如：我们已经知道了一个子串内有重复字符了，那么包含这个子串的串肯定也就不考虑了．但是暴力法并没有略过这种情况．

所以，我们引进了一个处理字符串问题时常用的方法：**滑动窗口**．

![在这里插入图片描述][20181210120618406.png]

所谓滑动，就是我们给字符串上标记了两个指针ｉ，ｊ，通过移动这两个指针，来获取两指针间的子串，并进行操作．

以上面的　ａｂｃａｄ为例，ｉ，ｊ一开始都指向ａ,将ａ放入HashSet中，ｊ向后移动

![在这里插入图片描述][20181210121450944.png]

然后判断ｂ是否在HashSet中，不在，所以将ｂ也加入HashSet中，ｊ继续向后移动  
![在这里插入图片描述][20181210121558136.png]  
ｃ也不在HashSet中，继续添加，ｊ向后移动

![在这里插入图片描述][20181210121628147.png]

这时，又碰到了一个ａ，我们判断ａ已经存在于HashSet中了，怎么办呢？  
此时，ｊ不动，remove掉HashSet中ｉ所在位置的元素，并让ｉ自增，继续判断

![在这里插入图片描述][20181210121747933.png]  
此时的HashSet中只有｛ｂ，ｃ｝　碰到了ａ，不在HashSet中，所以继续添加，j++；

![在这里插入图片描述][20181210121834981.png]  
最后ｄ也不在HashSet中，添加并自增　到ｊ＝５;

那么最长的子串不就是刚出现的ｂｃａｄ　，长度为　j - i = 5 - 1 = 4;,因为ｊ已经到头了，所以结束并返回

以上大致就是滑动窗口的思想了，滑动窗口在处理有关字符串的子串的问题上经常使用，大家可以通过多做题去掌握．

滑动窗口实现代码:

/**
         * 2.滑动窗口法:使用一个HashSet ,通过判断下一字符是否存在与Set中,从而移动子串左右边界的指针,获取最长子串
         * 时间复杂度O(2n) = O(n)
         */
        public int slideWindow(String s) {
            int length = s.length();
            Set<Character> set = new HashSet<>();
            int ans = 0;
            int i = 0, j = 0;
            while (i < length && j < length) {
                if (!set.contains(s.charAt(j))){
                    set.add(s.charAt(j++));
                    ans = Math.max(ans,j - i);
                } else {
                    set.remove(s.charAt(i++));
                }
            }
            return ans;
        }

最后一个问题：我们现在的方法是不是最优的呢？也不是．仔细想想：如果在遇到出现重复字符的时候，ｉ不是remove再自增，而是直接找到上一个对应重复字符的位置，remove再自增，这样效率也可以提高很多，不过这样我们就需要用额外的空间去保存每个字符有没有出现过，并且在哪个位置出现的．我们可以使用ＨashMap来优化

/**
         * 3.进一步优化后的滑动窗口
         * 思路:使用Map记录j的重复字符的位置j0,然后不用i++,直接让i=j0+1;
         * 时间复杂度:O(n)
         */
        public int optSlideWindow(String s) {
            int length = s.length();
            int ans = 0;
            Map<Character,Integer> map = new HashMap<>();
            for (int i = 0, j = 0; j < length; j++) {
                if (map.containsKey(s.charAt(j))) {
                    i = Math.max(map.get(s.charAt(j)),i);
                }
                ans = Math.max(ans,j - i + 1);
                map.put(s.charAt(j),j+1);
            }
            return ans;
        }

[20181210120618406.png]: /images/20220406/c68c9d896aa74b6daa51f65366456de6.png
[20181210121450944.png]: /images/20220406/37741b6f54894a70b3e17bdcb161b369.png
[20181210121558136.png]: /images/20220406/e8f917b27b924d21a1f72707b99e54d1.png
[20181210121628147.png]: /images/20220406/bf692738aa4446f28d194a1cbb920b47.png
[20181210121747933.png]: /images/20220406/fa8c06d913eb48bea6bf3b3540088323.png
[20181210121834981.png]: /images/20220406/acd55efd0dd54d88bd82cc5239b7c1a0.png