乐趣区

查找一个字符串中最长不含重复字符的子字符串计算该最长子字符串的长度

jiezi

前言：

算法题：查找一个字符串中最长不含反复字符的子字符串，计算该最长子字符串的长度；

上面将应用 滑动窗口 办法实现，并通过对滑动窗口算法一步步进行优化，使其空间和工夫的耗费一步步升高；

什么是滑动窗口？

滑动窗口：个别是指 运行在一个大数组上的子数组，该大数组是一个底层元素汇合。

例如：假如有大数组 [a b c d b e f d n]，设定一个大小为 3 的小数组 为 滑动窗口；则存在上面的窗口：

[a b c]
  [b c d]
    
      [d b e]
        [b e f]
          [e f d]
            [f d n]

滑动窗口重要性质：

  1. 滑动窗口个别示意成一个 左闭右开区间。
  2. 窗口的左边界（指针 i）和右边界（指针 j）永远只能向右挪动，而不能向左挪动。

如图：

应用滑动窗口解题

1、未优化的滑动窗口实现：

没有任何优化的滑动窗口实现；

通过 指针 i 和 指针 j 一直的向左挪动，造成了一个个的窗口，并且在将窗口的字符寄存到了 Set 汇合中，应用 Set 汇合判断 行将 进入窗口中的字符（也就是指针 j 挪动到指向的字符）是否在窗口曾经存在；

  1. 如果曾经存在：则计算此时窗口的大小，并将寄存窗口字符的 Set 汇合清空（清空是为了寄存下个窗口的字符），最初将 指针 i 向左挪动一位，而后指针 j 也指向指针 i 的地位。
  2. 如果是不存在：则将此字符寄存到 Set 汇合窗口字符中。
1.1、看图了解：

1.2、代码实现：
public class LeetCode {public static int lengthOfLongestSubstring(String s) {if (s == null){return 0;}
        if (s.length() == 1){return 1;}

        // set 用来存储窗口的字符
        Set<Character> set = new HashSet();

        // 指针 i
        int i = 0;
        // 指针 j
        int j = i;
        // 最大长度
        int max = 0;

        char[] sc = s.toCharArray();
        while(j < sc.length && i <= j){
            // 当字符没在窗口中
            if (!set.contains(sc[j])){set.add(sc[j]);
                // 指针 j 挪动
                j++;
            }else {
                // 如果字符在窗口中时, 失去以后窗口中的字符个数
                int size = set.size();
                if (max < size){max = size;}
                // 将 set 中存储的字符清空
                set.clear();
                // 指针 i 挪动
                i++;
                // 指针 j 挪动到指针 i 的地位
                j = i;
            }
        }
        // 当指针 j 挪动到字符串尾部时, 窗口中可能还存在字符
        if (set.size() > max){max = set.size();
            set.clear();
            set = null; // help GC
        }

        return max;
    }


    public static void main(String[] args) {System.out.println(lengthOfLongestSubstring("abcdbefdn"));
    }

}
1.3、执行成果（来自 LeetCode）：

1.4、未经优化的滑动窗口的毛病：

毛病一：

存在很多无用的反复的 滑动窗口；

例如：字符串 abcdbefdn，依据下面实现的滑动窗口办法，会失去以下窗口：[a b c d]、[b c d]、[c d b e f]、[d b e f]、[b e f d n] 这 5 个滑动窗口；上面错位展现更直观，会发现 [b c d]、[d b e f] 这两个滑动窗口显然被蕴含在其之前的窗口中，它们被反复统计了。

[a b c d]

  [b c d]

    [c d b e f]

      [d b e f]

        [b e f d n]

毛病二：

存储 滑动窗口中 字符的 Set 汇合存在重复 清空，再次存入字符的状况；并且存在字符被反复存入 Set 汇合中。

2、优化后的滑动窗口实现：

优化点：

  1. 间接将指针 i 指向呈现的反复字符的地位，滑动窗口大小为（j – i），这样就将无用的反复的 滑动窗口 跳过，这样会大大缩短执行工夫；
  2. 寄存滑动窗口的字符容器改为 Map 汇合，key 为 字符，value 为字符下标；并且不再清空集合了，而是遇到反复字符后，更新此字符的下标地位；

    例如：一开始 字符 b 在 map 汇合中的 value 地位为 1，当再次遇到下标为 3 的字符 b 后，将 map 汇合中的 value 下标 由 1 改为 3；

2.1、看图了解：

2.2、代码实现：
public class LeetCode {public static int lengthOfLongestSubstring(String s) {if (s == null){return 0;}
        if (s.length() == 1){return 1;}
        // map 用来存储窗口字符, key 是字符, value 为字符在字符串中的下标地位
        Map<Character, Integer> map = new HashMap<Character, Integer>();

        // 指针 j
        int j = 0;
        // 反复字符的地位, 默认为 -1
        int i = -1;
        // 最大长度
        int max = 0;

        char[] sc = s.toCharArray();
        while(j < sc.length){if (map.containsKey(sc[j])){
                // 获取 map 中反复字符的地位
                int index = map.get(sc[j]);
                if (index > i){i = index;}
            }
            // 指着 j - 反复字符的地位 = 以后窗口的大小
            if ((j-i) > max){max = j-i;}
            // 如果 map 中存在反复字符的话, 这里是将字符的地位进行更新 ; 如果不是反复字符的话，就间接寄存到 map 中
            map.put(sc[j], j);
            j++;
        }
        map.clear();
        map = null; // help GC

        return max;
    }

    public static void main(String[] args) {System.out.println(lengthOfLongestSubstring("abcdbefdn"));
    }
}
2.3、执行成果（来自 LeetCode）：

下面就是通过了代码优化后失去的执行成果，发现执行工夫大大缩短了；然而这可能还不是最优的，可能还存在最优的办法。

❤不要遗记留下你学习的脚印 [点赞 + 珍藏 + 评论]嘿嘿ヾ

所有看文章不点赞都是“耍流氓”，嘿嘿ヾ (◍°∇°◍)ﾉﾞ！开个玩笑，动一动你的小手，点赞就完事了，你每个人出一份力量(点赞 + 评论) 就会让更多的学习者退出进来！非常感谢！~ω~=

退出移动版