从零开始刷Leetcode day02 无重复字符的最长子串(Longest Substring Without Repeating Characters)

无重复字符的最长子串(Longest Substring Without Repeating Characters)-java解法

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例1:

输入: “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例2:

输入: “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

暴力解法：

• 通过两个for循环，算出每个字符开头的不含有重复字符的 最长子串 的长度。

  时间复杂度： O(n²)

  代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.equals("")||s.length() ==0){
            return 0;
        }if(s.equals(" ")||s.length() == 1){
            return 1;
        }int max = 1;
        for(int i =0;i<s.length();i++){
            Map<Character,Integer> map = new HashMap<>();
            map.put(s.charAt(i),0);
            int count = 1;
           for(int j =i+1;j<s.length();j++){
            if(map.containsKey(s.charAt(j))){
                break;
            }else{
                map.put(s.charAt(j),0);
                ++count;
            }}max = count>max? count:max;
        }return max;
    }
}
           

滑动窗口解法：

• 每次在[start，end]中如果有重复的，我们的做法是更新窗口从end重新开始，这种方法要求定义一个hashmap保存字符到索引的映射，并且每次都会更新map的值
• 定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1，表示从字符位置后一个才开始不重复

• 定义不重复子串的开始位置为 start，结束位置为 end

  随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符

• 无论是否更新 start，都会更新其 map 数据结构和结果 ans。

  代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start =0;
        int res =0;
        Map<Character,Integer> map = new HashMap<>();
        for(int end =0;start<s.length() &&end<s.length();end++){
            if(map.containsKey(s.charAt(end))){
                start = Math.max(start,map.get(s.charAt(end))+1);
            }map.put(s.charAt(end),end);
                res = Math.max(end-start+1,res);
         }return res;
    }
}
           

说明：

start=Math.max(map.get(s.charAt(end)),start);判断max的意义。

举例字符串为pwwkewp，当我们检查到最后一个p的时候，如果我们没有判断max的这个步骤，那么start就会回到1的位置，所以说为了防止这种情况出现，需要使用max。