glmapper

每天一道算法题:无重复字符的最长子串

字数统计: 883阅读时长: 3 min
2018/11/10 Share

题目

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

示例:

  • 给定 “abcabcbb” ,没有重复字符的最长子串是 “abc” ,那么长度就是3。

  • 给定 “bbbbb” ,最长的子串就是 “b” ,长度是1。

  • 给定 “pwwkew” ,最长子串是 “wke” ,长度是3。请注意答案必须是一个子串,”pwke” 是 子序列 而不是子串。

方案1

思路:

  • 字符对应的数字作为下标

  • 初始化一个255的boolean作为所有可能出现的字符对应的存在可能性,不存在重复的均为false,存在重复的,则对应的下标置为true。

  • 两个指针进行移动,前指针先不动,后指针移动并根据当前字符对应整数下标是否为false或者true进行判断。如果是false,则表示没有重复,则指针向后移动一位;如果为true,表示存在重复,则后指针停止移动,并计算当前字串长度,且将boolean数组重置,第一个指针向前移动一位,后指针指向当前前指针。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    class Solution {
    public int lengthOfLongestSubstring(String s) {
    int len = 0 ;

    if (s==null || s.length()== 0 )
    {
    return 0;
    }
    if (s.length() == 1){

    return 1;
    }

    int firstPoint = 0;
    int nextPoint = 0;

    boolean[] exist=new boolean[255];

    while (nextPoint < s.length()&&firstPoint <s.length()){

    int currMax = 0;
    int index = s.charAt(nextPoint)-0;
    while (exist[index] == false&&nextPoint<s.length()){
    exist[s.charAt(nextPoint)-0] = true;
    nextPoint++;
    if (nextPoint < s.length()){
    index = s.charAt(nextPoint)-0;
    }

    }

    currMax = Math.max(currMax,nextPoint-firstPoint);
    firstPoint++;
    nextPoint=firstPoint;
    len = Math.max(len,currMax);
    for (int i = 0 ; i < 255 ; i++)
    {
    exist[i] = false;
    }

    }

    return len;
    }
    }

方案2

思路:

以一个hashmap作为辅助,map的key存储的是字符,value存储的是该字符当前的位置,首先设置一个头指针,指向字符串开头,那么从开始遍历字符串,如果map当中不包含这个字符,那么用这个字符当前所在的位置减去头指针的位置,然后与最大长度做比较,选打的成为最大长度,然后把当前字符的以及位置放入map,以abba为例,头指针指向a,当前为a,那么长度为1,map。put(‘a’,0),当前为b,那么长度为2,map.put(‘b’,1),如果说map中存在当前字符,那么把头指针指向,头指针当前的位置与map中存储该字符位置的下一个位置当中的较大者,成为新的头指针位置,比如当走到第二个b的时候,那么头指针原来是0,当前map中存放b的位置是1,那么头指针指向2,所以长度为1,比最大长度小不进行替换,最后将当前的字符及位置放入map,现在是map.put(‘b’,2),然后走到了a,那么当前map中a的位置是0,那么它的下一个位置是1,与当前头指针位置2相比,小于当前头指针的位置,那么头指针不跟新,所以长度为2,与最大长度相等,所以不替换,最后求出最大长度为2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int lengthOfLongestSubstring(String s) {  
Map<Character,Integer> map=new HashMap<Character,Integer>();
int maxLength=0;
int now=0;
for(int i=0;i<s.length();i++){
if(map.containsKey(s.charAt(i))){
now=Math.max(map.get(s.charAt(i))+1,now);
if((i-now+1)>maxLength){
maxLength=i-now+1;
}
}else{
if((i-now+1)>maxLength){
maxLength=i-now+1;
}
}
map.put(s.charAt(i), i);
}
return maxLength;
}

原文作者:GuoLei Song

原文链接:http://www.glmapper.com/2018/11/10/leetcode5/

发表日期:November 10th 2018, 1:34:51 pm

更新日期:November 10th 2018, 1:35:15 pm

版权声明:转载请注明出处

CATALOG
  1. 1. 题目
  2. 2. 方案1
  3. 3. 方案2