dtcms插件 树莓派USB SQLMAP 父子元素 acm mtu原理 request gtk vue网站模板 ajax的get请求 大数据驾驶舱 最新更新国内最快的dns 录音棚设备一套多少钱 android调试工具 爬虫数据清洗 hadoop环境变量配置 flutter项目案例 mysqlinsert python操作mongodb python的random函数 python基本语法 python的def java类与对象 java入门教程 java求和 java接口的使用 javascript基础 php连接mssql 迷宫解锁 电池救星 js倒计时代码 backtrack3 显示器面板类型 win10wifi 只狼全鬼佛 逗号的作用 appdata是什么文件夹 键盘灯怎么关 js回调函数 画图橡皮擦怎么放大
当前位置: 首页 > 学习教程  > 编程语言

每日一道LeetCode——无重复字符的最长子串

2020/9/19 16:26:55 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目:

在这里插入图片描述

我的解法:

设定起始指针,利用HashSet判断重复,每次找到重复元素停止,起始指针右移。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int longest_length = 0;
        Set<Character> set = new HashSet<Character>();

        int start_index = 0;

        if (s.length()==0){
            return 0;
        }else if (s.length()==1){
            return 1;
        }else{
            while(start_index < s.length()){
            for (int i = start_index; i<s.length() && !set.contains(s.charAt(i)); i++){
                set.add(s.charAt(i));
            }

            if (set.size()>longest_length){
                longest_length = set.size();
            }
            set.clear();
            start_index++;
            }
        }

            return longest_length;
        
    }
}

但是比官方解法运行时间复杂度高很多,上面是我的解法,下面是官方解法。
在这里插入图片描述

官方题解:

双指针:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合,记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格,移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

本文链接: http://www.dtmao.cc/news_show_200428.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?