不含重复字符的最长子字符串

? ? ? ? 要找出不含重复字符的最长子字符串，可以用一个哈希表统计子字符串中字符出现的字数，出现一次即哈希表中对应位置的数值为1，未出现即为0，重复了那么它的值会比1大。

? ? ? ? 还是使用滑动窗口的思想。若两指针之间的子字符串无重复字符，那么移动右指针，然后判断新的字符在子字符串中有没有出现，如果还是没有则继续移动右指针；如果包含重复字符则移动左指针，删除最左边的字符，如果还是包含重复字符就继续移动左指针，如果不包含重复字符，则移动右指针添加新字符。

    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        // 假设只包含ASCII码，即256种字符
        int[] counts = new int[256];
        int i = 0;              // 右指针
        int j = -1;             // 左指针
        int longest = 1;        // 记录结果
        for (; i < s.length(); i++) {
            // 添加新字符
            counts[s.charAt(i)]++;
            while (hasGreaterThan1(counts)) {
                // 子字符串中有重复字符则移动左指针直至子字符串中没有重复的字符
                j++;
                counts[s.charAt(j)]--;
            }
            longest = Math.max(i - j, longest);
        }
        return longest;
    }

    // 判断子字符串中是否有重复的字符
    private boolean hasGreaterThan1(int[] counts) {
        for (int count : counts) {
            if (count > 1) {
                return true;
            }
        }
        return false;
    }

????????这个算法时间复杂度是O(n)，但每次调用函数hasGreaterThan1都要扫描一遍数组counts，这个数组长度是256，即使是常数还是有点大。因此下面介绍一种避免多次遍历哈希表的解法。

    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }

        int[] counts = new int[256];
        int i = 0;
        int j = -1;
        int longest = 1;
        int countDup = 0;       // 记录子字符串中重复字符的个数
        for (; i < s.length(); i++) {
            counts[s.charAt(i)]++;
            // 判断新加入的字符有没有重复
            if (counts[s.charAt(i)] == 2) {
                // 重复即标记
                countDup++;
            }
            while (countDup > 0) {
                // 进入该循环说明新加入的字符重复了，需移动左指针
                j++;
                counts[s.charAt(j)]--;
                if (counts[s.charAt(j)] == 1) {
                    // 数组中新加入字符对应位置的数值变为1说明已删除重复字符
                    // 可以退出循环了，取消标记
                    countDup--;
                }
            }
            longest = Math.max(i - j, longest);
        }
        return longest;
    }

????????这个解法时间复杂度同样是O(n)，但相比前一个解法避免了重复扫描数组counts，因此时间效率有所提高。

? ? ? ? 下面是另一种思路相似，但实现方式不同的另一种解法。时间复杂度也是O(n)。

    public int lengthOfLongestSubstring(String s) {
        int ans = 0;            // 记录结果
        int left = -1;          // 左边界
        int[] map = new int[256];
        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i);
            // 如果 map[ch] - 1 大于当前的 left，
            // 说明字符 ch 在当前的无重复字符子串中出现过（若没出现map[ch]的值是0）
            // 并且出现的位置在当前的子串范围内
            int index = map[ch] - 1;
            if (index > left) {
                // 出现重复时，更新左边界以确保子串中没有重复字符
                left = index;
            }
            // 不用填充成-1，而是记录字符在字符串中的位置
            map[ch] = i + 1;
            // 更新最长无重复字符子串的长度
            ans = Math.max(i - left, ans);
        }
        return ans;
    }