你的位置:首页 > Java教程

[Java教程]【leetcode】3. Longest Substring Without Repeating Characters


题目描述:

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

解题思路:

这个题我认为还是比较有难度的,解题的关键在于理解对于一串数字a[0],a[1],……a[m],……a[n],……;若a[m]=a[n],则这两个字符间可能出现的最大不重复字符列长度为n-m;所以我们可以用一个数组来记录起始位置与扫描位置间出现过的字符的数组array。若有重复,要做以下两步:1,计算pos-from,并与当前找到的最大值max作比较;2把起始位置移动到位于前面的重复字符的下一个位置(即如果第3个位置与第7个位置重复,则把from设为4),并且将前后两个from之间出现的字符在array中清空。以此类推,直至遍历完字符串。

代码如下:

public class Solution {  //应该考虑到字符串中的值不只是a-z,所以数组的大小不应该只设成26  public static int lengthOfLongestSubstring(String s) {    if(s.length()==0||s.length()==1)      return s.length();    if(s.length()==2){      if(s.charAt(0)==s.charAt(1))        return 1;      else        return 2;    }    int max = -1;    int[] array = new int[256];    int from=0;    char ch = s.charAt(0);    array[ch]++;    for(int i=1;i<s.length();i++){      ch=s.charAt(i);      if(array[ch]!=0){        int len = i-from;        if(max<len)          max=len;        for(int j=from;j<i;j++){          char c = s.charAt(j);          if(c!=ch){            array[c]=0;          }          else{            from=j+1;            break;          }        }      }      else{        array[ch]++;      }    }    if(s.length()-from>max)      max=s.length()-from;    return max;  }}