从零打卡leetcode之day 4--无重复最长字符串

帅地

发布于 2018-08-30 12:06:58

8040

发布于 2018-08-30 12:06:58

文章被收录于专栏：苦逼的码农

前言

深知自己在算法方面上很菜，于是打算通过打卡的方式，逼自己一把。每天在leetcode上打卡，并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路，那么，别犹豫了，上车吧，一起学习一起探讨。

说明：有点抱歉，昨晚发的记得有写题目描述，但不知为啥，题目描述丢失了，可能是自己突然不小心删除了。

题目描述：

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

示例：

给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。

给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。

给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

解题过程:

方法一：暴力版本

显然，对于这道题我们可以像以往一样，遍历所有子串，对于这个方法，我相信大家都能想到，我就直接贴代码了。如下

//三个for暴力解决
    public static int lengthOfLongestSubstring(String s) {
        int max = 0;
        int temp = 0;
        char[] arr = new char[s.length()];
        for(int i = 0; i < s.length(); i++){
            arr[i] = s.charAt(i);
            temp = 1;
            for(int j = i + 1; j < s.length(); j++){
                int flag = 0;//用来判断s[j]是否在arr中
                for(int k = i; k < i + temp; k++){
                    if(arr[k] == s.charAt(j)){
                        flag = 1;
                        break;
                    }
                }
                if(flag == 1){ break;//重复
                } else {
                    arr[i+temp] = s.charAt(j);
                    temp++;
                }
            }
            if(temp > max){
                max = temp;
            }
        }
        return max;
    }

前面两个for循环用来遍历所有子串，第三个for循环用来判断字符s.charAt(j)是否在子串中。

方法二：各种优化

优化策略1：大家想一个问题，对于第三个循环，我们在数组里查找该数组是否拥有某个字符，这个查找的过程的时间复杂度是O(n),我们是否有其他什么方法把查找的过程的复杂度降低到O(1)？

前几次我们都有用过hashMap来进行映射，实际上这里一样可以用hashMap来保存子串，然后再判断s.charAt(j)是否子串中，这样我们就可以把查找过程的复杂度降低到O(1)了。

优化策略2：假如给你一个字符串：

"abcdca"

我们在遍历子串的过程中，最开始我们从第一个元素'a'开始遍历，当我们遍历到'abcd'时，在继续查找的时候遇到'c'，此时"abcd"里面已经有'c'了，此时该子串查找完毕。此时长度为4，继续下一个子串的查找。

注意：我们继续下一个子串查找的时候，是从第二个元素'b'开始的。可是大家想一个问题，真的有必要从第二个元素'b'开始查找吗？，假如我们从'b'开始的时候，遍历到"bcd",继续遍历时又会再次遇到'c'，此时长度为3。比上一个子串4的长度小。

实际上，我们是没有必要从第二个元素开始查找的。我们直接从'd'开始查找就可以了，也就是说，如果 s[j]s[j] 在 [i, j)[i,j) 范围内有与 j'j′ 重复的字符。我们再下一次寻找子串时，直接从j'+1的位置开始就行了。如果你不是很理解为啥会这样的话，可以找一些元素模拟一下勒。

优化策略3：我们每次在寻找子串的时候，会把子串放进hashMap里，假如我们要寻找下一个子串的话，理论上是需要把hashMap里面的元素给清空，然后再用来放置新的子串的。

但实际上，是不需要这样子的，hashMap里面的元素是可以重复利用的。先上代码吧，然后我在画图解释下优化策略三。如下：

//用hashMap映射
    public static int lengthOfLongestSubstring2(String s) {
        int max = 0;//保存最长子串的长度
        //用来记录子串是从哪个下标开始的
        int i = 0;
        Map<Character, Integer> map = new HashMap<>();

        for(int j = 0; j < s.length(); j++){
            if(map.containsKey(s.charAt(j))){
                //从第一个重复元素的后一个开始
                i = Math.max(map.get(s.charAt(j))+ 1, i);
            }
            //j - i + 1 表示计算此时子串的长度
            max = Math.max(max, j - i + 1);
            map.put(s.charAt(j), j);
        }
        return max;
    }

假设字符串为"abcba"，下面演示hashMap中元素的变化情况。

当j = 2。