提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【刷题计划】无重复字符的最长子串

2023-03-31 10:32:26 时间

由于疫情，从今天开始在家远程办公，虽然远程看似不需要出门，但是还是又很多不便

  • 吃饭是个大问题，以前在公司食堂吃，到点去吃，现在要么自己做，要么外卖都是很麻烦
  • 工作时间变长，在公司十到点就去赶班车，在家都没有时间概念，同时感觉任务也更多大家都在加班，内卷更严重了

唉，抽出时间刷题太难了

刷了又不会，会了也记不住，记住了新题型还是不会，好要不要刷题呢？

1今日题目

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

示例 1:

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

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

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

输入: s = "" 输出: 0

思路

这道题难度是中等，我觉得挺难的，如果没接触过，估计很难在较低的算法复杂度下做出来，

主要考察滑动窗口算法

听起来“滑动窗口”很牛逼，其实就是类似双指针，

在两个指针之内的是符合条件的元素

如果遇到不符合条件得元素则两个指针向右移动，剔除最左边元素

比如abc是一个窗口，当再遇到a时，窗口内变成bca

代码实现如下，算法复杂度为O(n2)

public static int lengthOfLongestSubstring2(String s) {
    if (s.length() == 0) {
        return 0;
    }
    int result = 0;
    int left = 0;
    int right = 0;
    int length = 0;
    char[] data = s.toCharArray();
    List<Character> subString = new ArrayList<>();
    while (right < data.length) {
        int index = subString.indexOf(data[right]);
        while (index >= 0) {
            result = Math.max(result, right - left);
            subString.remove(0);
            length = subString.size();
            left++;
            index = subString.indexOf(data[right]);
        }
        length++;
        subString.add(data[right]);
        right++;
    }
    return Math.max(result, length);
}

优化1

public int lengthOfLongestSubstring3(String s) {
    if (s.length() == 0) {
        return 0;
    }
    Set<Character> subString = new HashSet<>();
    int result = 0;
    int left = 0, right = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        while (subString.contains(c)) {
            subString.remove(s.charAt(left));
            left++;
        }
        subString.add(c);
        right++;
        result = Math.max(result, subString.size());
    }
    return result;
}

优化2

上面实现的方案，在判断当前字符是否出现过时每次都是从前面遍历过数据中再次遍历

这种效率肯定不高，所以考虑通过hash表进行优化

public static int lengthOfLongestSubstring(String s) {
    int result = 0;
    if (s.length() == 0) {
        return result;
    }
    // 用map保存元素的位置，如果下一个字符在map中出现过
    // 证明窗口需要左移，窗口左指针为map中重复元素的下一个
    Map<Character, Integer> char2index = new HashMap<>();
    //start,end左右指针组成滑动窗口
    for (int start = 0, end = 0; end < s.length(); end++) {
        char element = s.charAt(end);
        if (char2index.containsKey(element)) {
            //char2index.get()的地方进行+1操作 ，此处是重点
            start = Math.max(char2index.get(element) + 1, start);
        }
        result = Math.max(result, end - start + 1);
        char2index.put(element, end);
    }
    return result;
}

2小结

滑动窗口的相关的题目还是很有规律可循的，明天争取抽个时间，对滑动窗口的题目做个总结与归纳，把相关题目梳理一遍。

相关文章