AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

LeetCode 3. 无重复字符的最长子串    原题链接    简单

作者: 作者的头像   optimjie ,  2020-05-03 02:17:45 ,  阅读 290


0


算法一:暴力

暴力找出所有的子串时间复杂度为$O(n^2)$,对于每个子串遍历一遍查看有无重复元素时间复杂度为$O(n)$,所以总的时间复杂度为$O(n^3)$,会超时,所以想一下如何做优化。

算法二:滑动窗口

将左右指针初始化成0,左指针每次向右移动1,右指针一直向右移动直到碰到重复的元素,这样一定能找到答案,因为这样是按照子串的开头遍历的,所以一定包含所有的情况。时间复杂度:因为i和j分别最多移动n次,所以为$O(2n)$

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> hash = new HashSet<>();
        int ans = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (i > 0) {
                hash.remove(s.charAt(i - 1)); // 因为i向右移动1,那么i-1位置上的字符从hash中删除
            }
            while (j < s.length() && !hash.contains(s.charAt(j))) { // 只要j不超过长度并且无重复元素则一直向右移动
                hash.add(s.charAt(j)); // 将该字符加到hash中
                j++;
            }
            ans = Math.max(ans, j - i); // 这里要注意的是不是j-i+1因为j停止时是包含重复元素的所以要再减去1
        }
        return ans;
    }
}

以右指针遍历,参考yxc

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        for (int j = 0, i = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                int k = i;
                i = map.get(s.charAt(j)) + 1;
                for (int u = k; u < i; u++) {
                    map.remove(s.charAt(u));
                }
            }
            map.put(s.charAt(j), j);
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息