leetcode 003. Longest Substring Without Repeating Characters

题目链接:https://leetcode.com/problems/longest-substring-without-repeating-characters/

原题描述:

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题目大意:给一个字符串,找出其中的最长连续无重复子串

题目解法(很经典的三种解法):

方法一(用map)

:滑动窗口,res记录最大无重复子串的长度,start为最大无重复子串的前一位,保证一个窗口向后移,每向后查找一个字符,看map中是否包含(查看包含的方法为该字符在map中的位置是否大于start),如果包含则更新该字符在map中的值(即位置)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int res = 0,start=-1;
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<len;++i){
            char c = s.charAt(i);
            if(map.containsKey(c)&&map.get(c)>start){//查看map中是否含有并且在当前子串中
                start=map.get(c);//如果在,则更新start位置,代表将左边字符移走
            }
            map.put(c,i);//更新在map中的位置
            res= Math.max(res,i-start);//找出最长子串
        }
        return res;
    }
}
方法二(用set):

用了set集合元素的不重复性,right代表右边界+1,left表示最长子串左边界,当循环一次时候,判断是否在set集合中,在,就将其从left开始删除,直到删除到该字符为止,否则将该字符添加到set中

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int left=0,right=0;//left表示最长子串左边界,right为右边界+1
        int res = 0;
        Set<Character> set = new HashSet<>();
        while(right<len){
            char c = s.charAt(right);
            if(set.contains(c)){
               set.remove(s.charAt(left++));//一直移除,直到set中不包含c字符
            }else{
                set.add(c);
                right++;
            }
            res = Math.max(res,right-left);//获取最大长度
        }
        return res;
    }
}

方法三(数组):

以上两种方法都是存字符,下面这种方法,将字符在AscII码中的位置存入数组,将值为该字符最晚出现的位置,每次循环记录字符出现的位置 ,并将其存入数组,如果该字符之前出现过,更新left位置,即字符的最左边界,依次循环即可。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0)  return 0;
        
        int[] occur = new int[128];
        Arrays.fill(occur, -1);
        
        int left = -1, right = 0, prev = -1, res = 0;
        for(right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            prev = occur[c];//记录该字符出现的位置
            occur[c] = right;//先存入该字符
            
            if(prev != -1) {//如果该字符出现过
                left = Math.max(prev, left);//更新left位置为这个字符最后出现的位置
            }
            res = Math.max(res, right - left);//每次循环结束,都要找出res最大值
        }
        return res;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容