LeetCode 每日一题 [3] 无重复字符的最长子串

LeetCode 无重复字符的最长子串 [中等]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

题目分析：

方法1：暴力法

检查所有的字符串，判断是不是含不重复的字符
提供一个判断这个字符串的字符是不是唯一的，如果是唯一的就返回 true，如果不是唯一的，就返回false。通过遍历所有的可能的字符串，得到结果，然后把距离计算出来，得到最大的值。时间复杂度O(n^3),空间复杂度O(min(n,m))
代码实现看下面：

方法2：滑动窗口

在暴力法中，我们需要检查所有的字符串，但是这是没有必要的，如果对于索引 i 到 j-1之间的字符串已经检查为不是重复的字符串，那么只需要检查 s[j] 是否在 Sij中即可。

要检查一个字符是不是在字符是不是在字符串中，我们可以检查整个字符串，这回产生一个O(n^2)的算法。

通过使用HashSet作为滑动窗口，我们可以使用O(1)的时间来完成对字符是否在当前字符串的检查

滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)[i,j) 向右滑动 11 个元素，则它将变为 [i+1, j+1)[i+1,j+1)（左闭，右开）。

回到我们的问题，我们使用HashSet存储当前窗口的字符串，然后 i j ，向右滑动直到小于字符串的长度，如果在滑动的过程中找到了一个重复的。那么就把最前面的一个字符干掉，然后继续活动，i或者j到达指定大小(字符串长度)，则停止滑动，返回结果。时间复杂度 O(2n) = O(n) 空间复杂度 O(min(n,m))

方法3：优化的滑动窗口

上述的方法作多需要指向2n个步骤，可以进一步优化为仅需要n个步骤，我们可以建立字符和索引的映射，而不是使用一个集合来判断一个字符是否存在。当我们找到重复的字符的时候，可以立即跳过该窗口。也就是说，如果 s[j]s[j] 在 [i, j)[i,j) 范围内有和 j’ 重复的字符，直接跳过[i,j']范围所有的元素，并将i变为j'+1

代码实现

public class LeetCode_03_NoRepeatLongestSubstring {

    public static void main(String[] args) {
        LeetCode_03_NoRepeatLongestSubstring lc = new LeetCode_03_NoRepeatLongestSubstring();
        int n1 = lc.lengthOfLongestSubstring_baoli("pasda");
        int n2 = lc.lengthOfLongestSubstring("pasda");
        int n3 = lc.lengthOfLongestSubstring_01("pasda");
        System.out.println(n1);
        System.out.println(n2);
        System.out.println(n3);
    }

    public int lengthOfLongestSubstring_baoli(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (allUnique(s, i, j)) {
                    ans = Math.max(ans, j - i);
                }
            }
        }
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        HashSet<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            char ch = s.charAt(i);
            if (set.contains(ch)) {
                return false;
            }
            set.add(ch);
        }
        return true;
    }

    public int lengthOfLongestSubstring_01(String s) {
        int n = s.length();
        HashSet<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }


    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        //创建Map窗口,i为左区间
        HashMap<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            // 如果窗口中包含当前字符，
            if (map.containsKey(s.charAt(j))) {
                //左边界移动到 相同字符的下一个位置和i当前位置中更靠右的位置，这样是为了防止i向左移动
                i = Math.max(map.get(s.charAt(j)), i);
            }
            //比对当前无重复字段长度和储存的长度，选最大值并替换
            //j-i+1是因为此时i,j索引仍处于不重复的位置，j还没有向后移动，取的[i,j]长度
            ans = Math.max(ans, j - i + 1);

            // 将当前字符为key，下一个索引为value放入map中
            // value为j+1是为了当出现重复字符时，i直接跳到上个相同字符的下一个位置，if中取值就不用+1了
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }

}

测试

4
4
4