【leetcode】不含重复字符的最长子字符串

一、题目描述

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

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

二、代码思想

如何表示连续子字符串 ？使用滑动窗口的思想来做，可以使用滑动窗口大小表示连续子字符串的大小。

如何判断字符重复 ？可以使用count数组来存放，各个字符的映射，如果对应位置出现了大于1的情况，代表重复。

注意判断边界值： “”、“a”、“abcd”、空串以及一个字符串的情况以及整个串都不重复的情况。

右指针何时停止 ？左指针何时能走 ？

当发现出现了字符重复的情况，右指针再走就没有必要了，因为题目是找出其中不含有重复字符的 最长连续子字符串 。

此时就应该让左指针走了，也就是说左指针走的情况是指，右指针遇到重复的情况，只要右指针遇到重复那么左指针就走，并且记录当前不重复字串大小也就是滑动窗口大小。

但是需要注意的是：“abbcdefg” 这样的情况，右指针指向第二个b之后，左指针走，并更新连续子字符串大小为 2 、1(取最大值)，但是之后并没有重复的了，也就是说进入不了左指针的 while 循环，那么最大大小就无法更新，所以我们再使用一个 res 来记录这种情况的窗口大小。

总结一下：

• 重复字符：去重问题可以考虑hash表与数组去重以及二进制去重。
• 子字符串：涉及到连续子串，也就是双指针left - right区域内的字符集合，也可以理解为滑动窗口。
• 子序列：子序列和子字符串是不一样的，子字符串是连续的，子序列可能不连续。但是还是看题目要求。

上述就是解题的信号，解题的时候能够根据题目特点选用自己手中的工具来解题。

三、代码题解

回头再看感觉当时解法并不优雅，不如结合HashSet + 双指针来做。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //使用计数数组统计字符出现次数
        //如果发现对应位置字符次数为 2 则代表出现重复字符
        int count[] = new int[127];
        int maxCount = 0; 
        //首先判断是不是空串
        if(s == "") return 0;
        //注意这里没有考虑到边界值：只有一个字符的情况
        if(s.length() == 1) return 1;
        //注意这里还没考虑到：如果整个字符串都没有重复字符的情况呢？
        //使用滑动窗口来找连续子字符串
        int l = 0;
        int flag = 0;
        int res = 0;
        for(int r = 0; r < s.length(); r++) {
            //此时，r 指针不能向右走了，也就是说 l 指针开始走
            ++count[s.charAt(r)];
            flag = 0;
            //代表此时开始有重复元素
            while(count[s.charAt(r)] > 1) {
                maxCount = maxCount > r - l ? maxCount : r - l;
                count[s.charAt(l++)]--;
                res--;
                flag = 1;
            }
            //如果后面字符都不重复，那么就进入不了 while 循环 ，maxCount就得不到更新
            //if((r == s.length() - 1) && flag == 0) return maxCount > r - l ? maxCount : r - l;
            res++; 
        }
        //return maxCount == 0 ? s.length() : maxCount ;
        return res > maxCount ? res : maxCount;        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34