求字符串中最长子串

这周开工第一天, 本地环境就出现了bug, 调试了一下午才解决, 今天就跟大家来简单分享一个算法吧.

 /**        * 求最大字符串的一个子串        * @Date 4:04 PM 2019/1/21        * "abcabcbb"       最大不重复长度是3        * "bbbbb"          最大不重复长度是1        * "pwwkew"         最大不重复长度为3    **/

方法一: 暴利解法

如果你一下想不出来最优的解法, 我们先来个简单粗暴的解法

1. 如果我们要求出最长的字符串, 那我们就把所有的子字符串列出来, 那如何才能列出出来所有的字符串呢, 那我们就需要从字符串上截取字段, 截取字段,那我们就需要一个开始start和一个结束end, 如果要取到所有的字段, 那我们0<= start < len(s), 那 start < end < len(s), 那这个就需要连个嵌套循环.

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) 内的字符是否都是唯一的，我们需要检查该范围中的所有字符。因此，它将花费 O(j - i)O(j−i) 的时间。

空间复杂度：O(min(n, m))O(min(n,m))，我们需要 O(k)O(k) 的空间来检查子字符串中是否有重复字符，其中 kk 表示 Set 的大小。而 Set 的大小取决于字符串 nn 的大小以及字符集/字母 mm 的大小。

方法二: 最优解

我们来拿一个字符串举例: 

abcdcbcbb

在子字符串[i, j]中, 当第二个c出现的时候, (即j = "c"), 我们在循环中, 现在是abcd, j不管怎么加, 其实都是没有意义的, 因为已经重复了, 这个时候, 其实我们应该做i + 1; 但是你发现, 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 < s.length(); 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;
    }