你的位置:首页 > Java教程

[Java教程][LeetCode] Longest Substring Without Repeating Characters


Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

 

     我自己觉得这道题还是很有难度的哈。

     这个思路要展开来不难,都能很快想到要用HashMap。但是在算法的问题上就需要细致的思考了。

     有几个思考错误可能很多人会犯。比如说很多人第一个反应以为是求两个重复的数之间的length。就以下面这组数来做例子。

     1,2,3,4,5,6,2,7,8,3,9,0,8,7

     很多人第一个反应就是要算2和2之间,3和3之间,7和7之间,8和8之间的length。

     但是题目上并没有说这种without repeating的length,首尾的前一位后一位必须一样啊。这就是典型的误区了。光顾着找重复的了。

     这也是为什么在代码中,Math.max()method在if statement外面的原因。

     代码如下。

public class Solution {  public int lengthOfLongestSubstring(String s) {    if(s.length()<2){      return s.length();    }    HashMap<Character,Integer> map=new HashMap<Character,Integer>();    int len=s.length();    int end=1;    int start=0;    int max=1;    map.put(s.charAt(0),0);    while(end<len){      if(map.containsKey(s.charAt(end))&&map.get(s.charAt(end))>=start){        start=map.get(s.charAt(end))+1; //since it's for length,so need +1      }      max=Math.max(max,end+1-start); //also for length,end +1      map.put(s.charAt(end),end);      end++;    }    return max;  }}