每日一题（4）：无重复字符的最长子串

开始

被教育了...暴力解法不可取

虽然我意识到了：

• 用HashSet判重
• 可以提前结束扫描

但是依旧没有改变这个算法时间复杂度贼高的本质。。

话不多说，看码

class Solution {
    String tempKing = "";
    int currStart = 0;
    int currEnd = 0;

    Set<Character> set = new HashSet<>();
    char[] cs;

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        cs = s.toCharArray();

        for (int i = 0; i < cs.length - tempKing.length() + 1; i++) {
            currStart = i;
            currEnd = currStart;
            while (currEnd < cs.length) {
                char c = cs[currEnd];
                if (!set.contains(c)) {
                    set.add(c);
                    currEnd++;
                } else {
                    i = currStart;
                    set.clear();
                    break;
                }
            }
            if (isKing()) {
                tempKing = newKing();
            }
        }

        return tempKing.length();
    }

    private boolean isKing() {
        return currEnd - currStart > tempKing.length();
    }

    private String newKing() {
        return new String(cs, currStart, currEnd - currStart);
    }
}

所谓一顿操作猛如虎，一看比分...

这道题我觉得可以再写一期了...正解是使用滑动窗口思路

真是一看就豁然开朗

真是吃了没文化的亏

明明工作中TCP协议发送数据包也用了滑动窗口算法 怎么就没想到呢

（其实想到了KMP算法但其实跟这个没啥关系）

也让我明白了下次要仔细审题，甚至要在脑海里先把结果跑一遍 观察下规律 才能找到最优解

好了散会 晚安各位明天见