Bolo  当前访客:9 管理登录

GeekTom | Blog

Be profound be funny or be quiet .

03 - 无重复字符的最长子串

2019-12-12 21:57:51 geektomya
0  评论    155  浏览

新的一天,开冲 🚀 🚀

题目描述

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

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

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

问题拆解

根据题目要求的最长子串,有一个基本的思路是遍历字符串,保存已经遍历过的字符到子串。每次遍历的时候首先判断该字符是否在已经遍历过的子串中,如果没有就将该字符串保存到已遍历集合。如果存在就获取已经遍历过的子串的长度,然后与之前的子串的最大长度做比较,取最大值做为当前的最大值,再清空已经遍历的集合。然后再从跟当前字符重复的字符开始遍历,最后遍历完后,返回已遍历的子串最大长度与已遍历的子串当前长度的最大值!我的代码如下:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //用map是因为当字符重复后,需要从前一个该字符后重新遍历,所以从map遍历
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        char sub[] = s.toCharArray();
        int result_length = 0;
        int j = 0;
        for(int i=0;i<sub.length;i++){
            if(map.containsKey(sub[i])){   
                result_length = Math.max(map.size(),result_length);
                j = map.get(sub[i]);
                map.clear();
                i=j;//切换到被重复的前一个该字符
            }else{
                map.put(sub[i],i);
            }       
        }   
        return  result_length = Math.max(map.size(),result_length);//解决最长子串是最后一个满足条件的子串
    }
}

这种方法虽然可以解决问题,但是可以发现,效率不太高,这里当我们发现了有重复的字符后,我们将遍历的当前位置指向了重复的前一个该字符后,这样导致了重复遍历。那么有没有一种方法,但发现有重复字符的时候可以不清除已遍历的所有字符,而是将重复的前一个该字符到之前的字符都删去。这时就可以不动当前遍历位置,从而继续遍历。方法肯定是有的,人们一般将这种方法称之为:滑动窗口法,解此题代码如下

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

标题:03 - 无重复字符的最长子串
作者:geektomya
地址:HTTPS://blog.zhqy.xyz/articles/2019/12/01/1575198610185.html
彧语:乾坤未定,你我皆是黑马!!!

发表评论




目录

TOP
取消