美文网首页AlwaysCode|坚持编程 坚持AC
LeetCode 3|无重复字符的最长子串

LeetCode 3|无重复字符的最长子串

作者: 蓝白绛 | 来源:发表于2019-01-18 11:12 被阅读0次

    前言

    如果你能找到这里,真是我的幸运~这里是蓝白绛的学习笔记,本集合主要针对LeetCode。这里我会记录刷leetcode的学习和思考的过程,如果和leetcode官方解题有雷同,那是当然会有的啦。我会在记录的同时配以图文解释,如果对大家有帮助,那就再好不过了。

    题目

    给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
    
    示例:(具体可在leetcode中查看)
    
    input:abcabcbb
    
    output:3
    

    思路

    暴力破解

    首先我们需要i和j用两层嵌套循环来遍历所有子串。对于每个子串,我们需要判断子串中是否有重复,也就是需要遍历该子串,那么这个时间复杂度是O(n^3)

    滑动窗口

    滑动窗口是数组/字符串问题中常用的抽象概念。i和j代表下标,[i,j)表示数组中ij-1的元素。开闭可自定义,但一般前闭后开。在此题中,如果从ij-1的子字符串[i,j)没有重复,那么我们只需要检查s[j]对应的字符是否已经在[i,j)中。我们用HashSet构造一个滑动窗口,将当前无重复的字符存在HashSet中。如果在hashset中,则i++,子串长-1,ans不动;如果不在hashset中,则j++,子串长+1,ans更新。此题只需要用更大的ans改写之前的ans就行,不需要输出最长的无重复子串是什么,用hashset没问题。附代码和图解如下。时间复杂度为O(n)

    class Solution {
        public int lengthOfLongestSubstring(String s) {
            HashSet<Character> set = new HashSet<>();
            int i = 0;
            int j = 0;
            int ans = 0;
            while(i<s.length() && j<s.length()){
                if(!set.contains(s.charAt(j))){
                    set.add(s.charAt(j));
                    j += 1;
                    ans = Math.max(ans, set.size());
                }else{
                    set.remove(s.charAt(i));
                    i += 1;
                }
            }
            return ans;
        }
    }
    
    leetcode 3|滑动窗口解法

    优化的滑动窗口

    上面滑动窗口的方法要不停的增加元素和移除元素,虽然我们已经利用hashset使增加元素和移除元素的时间复杂度尽可能低,但是我们还有方法可以加速。如果我们遇到一个重复的元素,i则可直接跳转到当前子串中重复元素的后一位,这在重复元素在子串中间时特别高效。优化的滑动窗口利用hashmap存储当前最长子串,并且不需要删除元素。当j增加一位的时候,我们检查s[j]是否在hashmap中,并查找map中对应的value值即可判断是否重复,如果重复,则i跳转到value+1。这里的一个关键问题是,我们不删除hashmap中的元素,如何判断遇到的新元素是否已经在当前最长子串中?这里非常欣赏leetcode官网的解答,代码如下。

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            Map<Character, Integer> map = new HashMap<>();
            for (int j = 0, i = 0; j < n; j++) {
                if (map.containsKey(s.charAt(j))) {
                    i = Math.max(map.get(s.charAt(j)), i);
                    //关键步骤,hashmap如何判断是否有重复。
                }
                ans = Math.max(ans, j - i + 1);
                map.put(s.charAt(j), j + 1);
            }
            return ans;
        }
    }
    

    这句代码的意思是如果s[j]在map中,获得s[j]对应的value值,如果value值小于当前i,则表示s[j]并未重复。大家可以好好体会这段代码,图解见下图。

    leetcode 3|优化的滑动窗口

    小结

    这是我刚开始在leetcode上刷题,所以参考了leetcode的官方解法,时间有限就不看更多解法了。这里官方解法中的hashmap解法个人认为非常精彩,对于实现滑动窗口有非常好的优化。

    结尾

    如果您发现我的文章有任何错误,或对我的文章有什么好的建议,请联系我!如果您喜欢我的图文,请点喜欢~*我是蓝白绛,感谢你的阅读!

    相关文章

      网友评论

        本文标题:LeetCode 3|无重复字符的最长子串

        本文链接:https://www.haomeiwen.com/subject/eivudqtx.html