欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeeCode3:无重复字符的最长子串

程序员文章站 2022-07-12 12:16:10
...

题目描述

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

解析

1.暴力法

    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        char[] ss = s.toCharArray();
        int len = ss.length;
        Set<Character> set = new HashSet<Character>();
        int max_len = 0;
        //for循坏依次从头开始找
        for(int i=0;i<len;i++){
            //清空set
            set.clear();
            //后面没有最优解
            if(len-i<max_len){
                break;
            }
            //存入map
            set.add(ss[i]);
            int temp_len = 1;
            int j = i+1;
            while(j<len&&!set.contains(ss[j])){
                set.add(ss[j]);
                temp_len++;
                j++;
            }
            //保存最大值
            if(temp_len>max_len){
                max_len=temp_len;
            }
            if(j==len){
                break;
            }
        }
        return max_len;
    }

2.滑动窗口

public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        char[] ss = s.toCharArray();
        int len = ss.length;
        Set<Character> set = new HashSet<Character>();
        int max_len = 0;
        //滑动窗口
        int i=0;
        int j=0;
        while(j<len){
            if(!set.contains(ss[j])){
                //不在set中
                set.add(ss[j]);
                max_len = Math.max(set.size(), max_len);
                j++;
            }else{
                //在set中
                set.remove(ss[i]);
                i++;
            }
        }
        return max_len;
    }