求字符串中最長子串

這周開工第一天, 本地環(huán)境就出現(xiàn)了bug,?調試了一下午才解決, 今天就跟大家來簡單分享一個算法吧.

 /**????????*?求最大字符串的一個子串        * @Date 4:04 PM 2019/1/21        * "abcabcbb"       最大不重復長度是3        * "bbbbb"          最大不重復長度是1        * "pwwkew"         最大不重復長度為3    **/

方法一: 暴利解法

如果你一下想不出來最優(yōu)的解法, 我們先來個簡單粗暴的解法

1. 如果我們要求出最長的字符串, 那我們就把所有的子字符串列出來, 那如何才能列出出來所有的字符串呢, 那我們就需要從字符串上截取字段, 截取字段,那我們就需要一個開始start和一個結束end,?如果要取到所有的字段, 那我們0<= start < len(s), 那?start < end

2. 為了求出所有子串中不重復的最長字符串, 我們可以使用一個集合來記錄元素, 遍歷所有的子串, 如果中間有元素重復, 那就返回最長的不重復的長度

pulibc class Solution {  public static int lengthOfLongestSubstring(String s) {        if (s == null || s.length() == 0) {            return 0;        }        int n = s.length();        int result = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                result = allUnique(s, i, j, result);????????????}        }        return result;    }    public static int allUnique(String s, int start, int end, int result) {        Set set = new HashSet<>();        int len = 0;        for (int i = start; i < end; i++) {            Character ch = s.charAt(i);            if (set.contains(ch)) {                return Math.max(len, end - start);            }            set.add(ch);        }        return len;    }}

復雜度分析

時間復雜度：O(n^3)O(n3) 。

要驗證索引范圍在 [i, j)[i,j) 內(nèi)的字符是否都是唯一的，我們需要檢查該范圍中的所有字符。因此，它將花費 O(j - i)O(j?i) 的時間。

空間復雜度：O(min(n, m))O(min(n,m))，我們需要 O(k)O(k) 的空間來檢查子字符串中是否有重復字符，其中 kk 表示 Set 的大小。而 Set 的大小取決于字符串 nn 的大小以及字符集/字母 mm 的大小。

方法二: 最優(yōu)解

我們來拿一個字符串舉例:?

abcdcbcbb

在子字符串[i, j]中, 當?shù)诙€c出現(xiàn)的時候, (即j = "c"), 我們在循環(huán)中, 現(xiàn)在是abcd, j不管怎么加, 其實都是沒有意義的, 因為已經(jīng)重復了,?這個時候, 其實我們應該做i?+ 1;?但是你發(fā)現(xiàn), i其實加1也是沒用的,?i其實可以直接移動到第一個d的地方就行了,就是第一重復的c的位置+ 1,??因為bcdc這個是沒有必要的,?i直接可以調到第一個c對應的下標 + 1開始就好了, 這樣的效率是最好的, 下面我們用hashMap來操作, 用hashmap來記錄,?key記錄字符, value記錄字符的下標.

// HashMap的做法    public static int lengthOfLongesSubstring(String s) {        if (s == null || s.length() == 0) {            return 0;        }        HashMapmap = new HashMap<>();        int res = 0;????????//?只需要移動一個j,?i是左邊移動的下標,?如果有重復,?直接賦值過去,?如果一直沒有重復,就是0????????for?(int?j?=?0,?i?=?0;?j?????????????if?(map.containsKey(s.charAt(j)))?{????????????????i?=?Math.max(i,?map.get(s.charAt(j))?+?1);            }            // 記錄字符串, key為字符, value為下標????????????map.put(s.charAt(j),?j);????????????//?計算兩個子字符傳的距離,????????????res?=?Math.max(res,?j?-?i?+?1);        }        return res;
    }