LeetCode 力扣 3.无重复字符的最长子串

妖狐艹你老母 2023-02-17 02:28 13阅读 0赞

题目：

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

> 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
> 
> 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
> 
> 示例 3: 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。  
>   
> 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

从示例 3 可以看出来，子串必须是连续的。

### 一、分析 ###

##### 分析： #####

1.  “滑动窗口”的思想比较容易想到，用两个指针 i 和 j；
2.  将 i 固定在开始，j 移动，如果没有重复则继续移动 j ，一旦重复就记录距离，这是一个“无重复字符”的子串的长度；
3.  接着 i 就可以直接跳到 j 的位置（因为 j 是重复元素），j 继续移动，重复上面的过程，更新每次的子串的长度。

##### 具体的实现来说： #####

1.  如果使用列表，在查找“有没有重复”的过程里，一般是要遍历前面已有的所有位置，那么在总共的两重循环下，时间复杂度会达到 O(n) ，好处是在找到重复之后就立刻知道重复的元素是谁，可以将 i 跳到 j ；
2.  如果查找“有没有重复”的过程希望复杂度位 O(1) 那么可以使用哈希表，但是哈希表的存储一般没有顺序，没法按下标，所以 i 的挪动只能“按值”将最早加入哈希表的那个字符删掉，也就是子串的最前面一个字符，这样外循环是连续的 O(n) ；
3.  让哈希表也能删除连续的好几个元素。

### 二、做法一（HashSet） ###

直接利用**数据结构 HashSet** ，我们以示例 1 来模拟过程，“abcabcbb”，要找出最长的子串：

“a b c a b c b b”

1.  **a**，加入集合；
2.  **b**，加入集合；
3.  **c**，加入集合；
4.  **a**，已经有 a 了，重复，此时子串最大长度是 3 。从集合删除最前面的 a ，此时剩下 b c；
5.  **a**，加入集合；
6.  **b**，已有 b ，重复，此时最长长度为 b c a 是3。从集合中删除最前面的 b ，此时剩下 c a；
7.  **b**，加入集合；
8.  **c**，已有 c ，重复，此时最长长度为 c a b 是3。从集合中删除最前面的 c，此时剩下 a b；
9.  **c**，加入集合；
10. **b**，已有 b，重复，此时最大长度为 a b c 是3。（虽然我们希望从集合中直接删除 a 和 b，毕竟直接从 c 开始才有意义。但是由于 set 无法记录下标，办不到，只能移除一个最前面的 a ，然后继续进行判断）。从集合中删除 a，此时剩下 b c；
11. **b**，已有 b，重复，此时最大长度是 b c 是2。从集合中删除 b，剩下 c；
12. **b**，加入集合；
13. **b**，已有 b，重复，此时最大长度是 c b 是2。从集合中删除 c，剩下 b（注意，仍然没办法直接删完）；
14. **b**，已有 b，重复，删除 b ，删除后集合已经空；
15. **b**，加入集合。

代码做法很简单：

*  外循环直接遍历字符串一次。
 *  内部先判断是否重复，如果重复，删除 Set 里最前面（逻辑上最前面）的一个元素。

我们需要额外的一个指针，遍历字符串的 i 是其中的一个，总是代表子串的开始，还需要一个 end 指针代表子串的最右边。

//对于整个s遍历一遍，时间复杂度为 O(n) 。
            for(int i=0;i<s.length();i++){
        
                if(i>0){
        
                    set.remove(s.charAt(i-1));
                }
                
                //最右边出现重复元素之后 end 还要后移，避免超范围用 end+1 来判断
                while(end+1<s.length() && !set.contains(s.charAt(end+1))){
        
                    set.add(s.charAt(end+1));
                    end++;
                }
                //更新ans，用下标之差来计算，由于上一步判断用的是 end+1 所以距离要+1.
                ans=Math.max(ans,end-i+1);
            }

加上初始化和特殊情况的判断，就可以写出完整代码.

ans 的初始值显然为 0，那么 end 的初始值应该为 0 吗？

考虑到开始 Set 为空，那么第一次执行 add 操作的时候， add( end+1 ) 加进去的是下标为 0 的字符，所以end的初始值应该设为 -1。

完整代码：

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            if(s.length()==1){
        
                return 1;
            }
            Set<Character> set=new HashSet<>();
            int ans=0;
            int end=0;
    
            for(int i=0;i<s.length();i++){
        
                if(i>0){
        
                    set.remove(s.charAt(i-1));
                }
    
                while(end+1<s.length() && !set.contains(s.charAt(end+1))){
        
                    set.add(s.charAt(end+1));
                    end++;
                }
                ans=Math.max(ans,end-i+1);
            }
            return ans;
        }
    }

### 三、利用ASCII码值新建哈希数组 ###

上一种方法的弊端我们已经讨论过，对于子串的开始指针 i 和结束指针 j ，找到重复之后就立刻知道重复的元素是谁，可以将 i 跳到 j，这一点做不到。

考虑到 ASCII 码值总共只有 128 个，所以我们可以用对应的码值，也就是 **charAt(i) 作为下标**，自己**创建一个哈希表**，用数组的值记录 “ 某一个字符**出现过的次数** ” ：

*  在“查找是否重复”的时候，根据下标取值，判读是否为 1 ，时间为 O(1) ；
 *  删除的时候，要**把 i 直接挪到 j**，可以用 i 和 j 之间**每一个 charAt(i) ，找到数组中的值然后 -1** ，这样也是 O(1) 的时间复杂度，并且**一次删除了所有多余的数字， i 的下一个开始位置就是 j 。**

如果阅读起来不容易，可以直接来看代码：

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
            int[] hashmap=new int[128];
            int ans=0;
            int n = s.length();
    
            for(int i=0,end=0;end<n;end++){
        
                hashmap[s.charAt(end)]++;
    
    			//只要 i 还没有到 end ，中间的这段字符都删除，也就是哈希表中的值 --
    			//while 结束的时候，i 到达 end 也就是上一个重复字符
                while(hashmap[s.charAt(end)]>1){
        
                    hashmap[s.charAt(i)]--;
                    i++;
                }
    
                ans=Math.max(ans,end-i+1);//当前这个不重复子串的长度和已有ans取最大值
            }
            return ans;
        }
    }

这段代码的核心就是 while 部分，假如是 “ a b c d c ” 的话：

*  hashmap\[ a \]++, hashmap\[ b \]++, hashmap\[ c \]++, hashmap\[ d \]++，ans一路增加到了 4 ，这段时间起始的 i 都没变;
 *  end = c，发现了重复，体现在 hashmap\[ c \]=2>1 了，进入while循环：
    
     *  hashmap\[ a \]- -，发现 hashmap\[ c \]没变化，还是=2>1
     *  hashmap\[ b \]- -，发现 hashmap\[ c \]没变化，还是=2>1
     *  hashmap\[ c \]- - ，发现hashmap\[ c \]变化了，1 不再 >1
     *  i 更新到了 end 在的位置
 *  继续下一个子串，开始就是 i 在 end 的位置