无重复字符的最长子串

题目

力扣链接：无重复字符的最长子串

题解

子串问题（或子序列问题）规律总结：必须以i位置结尾怎样怎样 或者 必须以i位置开始怎样怎样；把每个位置的答案求出了，最终答案就是所有答案中的最大值

子串跟子序列的区别：子串是必须连续的，子序列可以要求不连续

这个题就只有两个因素影响

• 上一个重复字符出现的位置在哪
• i-1位置结尾，往左推了多远

如何记录上一个重复字符出现的位置呢？可以用一个map，也可以自己用数组代替map。（建议能不用map的情况下，就不用map。虽然map的增删改查时间复杂度是O(1)，数组寻址比map查找，在常数时间上更快一点！下文会举例子测试）

自己用数组代替map，数组的长度如何确定呢？如果给定的字符串只有大小写字母，那么数组长度可以改为128；如果给定的字符串只有小写字母，那么数组长度可以改为26

为什么要记录i-1位置结尾的情况下，往左推了多远呢？

因为此题的答案就是上述两个影响因素谁离我当前位置近，谁就是答案！

并且记录i-1位置结尾的情况下，往左推了多远，还有一个好处。我们不需要生成一个dp数组，每次都查找一遍；可以只用有限几个变量来滚动记录。因为要求的无重复字符的最长子串的长度就是上述两个影响因素谁离我近，最后下标相减，最后取最大值就是答案。

代码

public int lengthOfLongestSubstring(String s) {
        if(s==null || s.equals("")){
            return 0;
        }
        char[] str=s.toCharArray();
        // 用数组代替map，常数时间会更快一点（map用来记录上一个重复字符出现的位置）
        // 如果给定的字符串只有大小写字母，那么数组长度可以改为128
        // 如果给定的字符串只有小写字母，那么数组长度可以改为26
        int[] map=new int[256];
        for(int i=0; i<256; i++){
            map[i]=-1;
        }
        int len=0;
        // pre记录i-1位置结尾的情况下，往左推，推不动的位置
        int pre=-1;
        int cur=0;
        for(int i=0; i!=str.length; i++){
            // i位置结尾的情况下，往左推，推不动的位置
            // pre(i-1位置的信息) 更新为 i位置的信息
            pre=Math.max(pre,map[str[i]]);
            cur=i-pre;
            len=Math.max(len,cur);
            map[str[i]]=i;
        }
        return len;
    }
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

时间复杂度分析

时间复杂度为O(N)，额外空间复杂度为O(1)

虽然申请了一个长度为256的数组，但是是固定长度，跟N没有关系，所以这个操作的空间复杂度是O(1)，此外还申请了几个变量，所以空间复杂度为O(1)

除了一个for循环，其余操作的时间复杂度都是O(1)，所以时间复杂度是O(N)

map和数组查找的效率比较

上文说过，两者的时间复杂度都是O(1)，但是数组寻址的常数时间比map更快一点。

可能用map查找的时候，JVM里面会有些缓存，所以区别不是
特别明显。

用毫秒看不出区别，用纳秒区别也不大，而且map竟然还快一点，可能是缓存的问题吧，本来还可以用微妙去试一下，到那时Java中没有直接获取微妙的方法，所以就没弄了，但是数组寻址确实是比map查找的常数时间更快一点，这一点毋庸置疑！