社区首页 >专栏 >刷题记录（LeetCode 100 热题系列）2

刷题记录（LeetCode 100 热题系列）2

原创

猎户星座1

修改于 2021-01-18 06:25:13

34200

代码可运行

文章被收录于专栏：Java StudyJava Study

运行总次数：0

代码可运行

文章谨记录自己的刷题过程，思路，仅目的用于自己的思路记录。

无重复字符的最长子串 LeetCode url (https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/)

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

示例 3:

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

题目有种之前做过，但是提交的时候是发现自己没有做过的，

自己的思路有点想 for for 两个for 循环 -》第一个for循环用于向下遍历字符串的每一位数 -》for 循环内去处理这层循环要处理的逻辑（也就是内层循环去判断是否以外循环的数值为起始位的子串，一旦出现重复就记录一下这次循环的子串长度） -》

比较每次以不同位置为起点的子串长度 -》能得到max 子串长度

自己是用内循环中每次 new string（）的方式，作为容器去记录每次内循环的子串长度，把判断方式抽取出了就成了大家所的滑动窗口。

 public int lengthOfLongestSubstring(String s) {
         int max = 0;
         char[] chars =  s.toCharArray();
        
        if(chars.length <=1 )
            return chars.length;

        for (int i =0 ; i< chars.length; i++ ){
            String maxString = "";
            for(int j = i; j< chars.length ; j++){

                if (maxString.indexOf(chars[j]) == -1 ){
                    maxString = maxString + chars[j];
                }else{
                    break;
                }
            }
             max = max > maxString.length() ?  max : maxString.length();
        }
              
        return max;
    }

自己也是看了leetcode 的官方解题才发现了自己的思路和官方也就是所谓的滑动窗口是这样的，滑动窗口这种解决办法出现的意义就是可以替代每次不维持滑动窗口的重复的创建从特定位置的开始的“窗口”。

官方题解：每次向右移动，减少窗口中的数据，更像是解决我每次在内循环中要的坐标向右移动更新，计算的都是内循环中移动后的子串长度


public int lengthOfLongestSubstring(String s) {
    
        int max = 0;
        if(s.length() <=1)
          return  s.length();

        int r = -1 ;  
        Set<Character>  set  = new HashSet();

        for(int i =0 ; i< s.length(); i++){
            if(i != 0){
                set.remove(s.charAt(i-1));
            }
            while(r+1 < s.length() && !set.contains(s.charAt(r+1))){
                // 不断移动右指针
                set.add(s.charAt(r+1));
                r++;
            }
            // 第i 到 r 位置的元素是一个 无重复的字符子串
            max = Math.max(max,r-i +1);
        }

        return max;
        

    }

map里面存放的为不会重复数字的窗口，因此移动时判断的是 map 维护的是只要移动过程中出现了冲突的数据，就要更新左侧的数据，不需要像多次的判断减少循环。

public int lengthOfLongestSubstring(String s) {
    
        if(s.length() <=1 )
           return s.length();

        HashMap<Character ,Integer>  map =  new HashMap<Character ,Integer>();  
        int max = 0;
        int left = 0;

        for(int i = 0 ; i< s.length(); i++ ){
            if (map.containsKey(s.charAt(i))){
                left =Math(left, map.get(s.charAt(i))+1);
            }
            // 如果相等的话就会被覆盖掉， 不相等就要被set 进去    
            map.put(s.charAt(i),i);
            max = Math.max(max , i-left +1);
        }
        return max;

    }