算法探索_无重复字符的最长子串

问题介绍：

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

示例 1:

输入:"abcabcbb"

输出:3

解释：因为没有重复字符的最长子串是“abc“，所以它的长度是3。

示例2:

输入:"bbbbb"

输出:1

解释：因为没有重复字符的最长子串是“b“，所以它的长度是1。

示例3:

输入:"pwwkew"

输出:3

解释：因为没有重复字符的最长子串是“wke“，所以它的长度是3。

请注意，你的答案一定是子串的长度，“pwke“是子序列，不是子串。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

解决过程：

先看看深海的提交历史:

如果你在网上查这个问题，有两种解决方案:双指针/动态规划

我在想，能不能用最粗暴、最简单的方式来解决这个问题

第一版提交很尴尬。提交后，执行加班。经过多次优化，提交通过

核心思路：

1.列出所有段落的可能性

2.判重所有可能性，得到所有不重复的段落

3.选择最长的不重复段落

加时后优化：（代码位置注释1，2）

1.判重优化：假如 待处理的段落长度 小于或等于当前 合法的最大长度，

然后跳出循环，因为即使它通过排重也没有意义；

2.遍历条件优化：在第二层循环I不变j++的情况下，如果某个内部出现重复字符，

所以未来的长度是没有意义的，因为它包含了关系。

最后经过两次优化，终于通过了提交

/*

     *作者:赵星海

     *时间:2020/7/22 10:26

     *用途:无重复字符的最长子串-最简单解法

     */

    public int lengthOfLongestSubstring(String s) {

                int y = 1;

                if (s.length() < 1) {

                    return 0;

                } else if (s.length() == 1) {

                    return 1;

                }

                boolean is;//2

                HashSet<String> hashSet = new HashSet<>();

                for (int i = 0; i < s.length(); i++) {

                    is = true;  //2

                    for (int j = i + 2;is&&j <= s.length(); j++) {  //2

                        if ((j - i) <= y) continue;//1

                        String x = s.substring(i, j);

                        hashSet.clear();

                        for (int k = 0; k < x.length(); k++) {

                            if (hashSet.add(String.valueOf(x.charAt(k))) == false) {

                                is = false;//2

                            }

                        }

                        if (is) {

                            if (x.length() > y) {

                                y = x.length();

                            }

                        }

                    }

                }

                return y;

        }