Level:
Medium
题目描述:
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
思路分析:
给定一个字符串,找到其长度最长的不重复子串,用滑动窗口的思想,设置窗口start,应尽量使窗口变大,从第一个字符开始遍历,遍历时,如果字符未出现过,在map中给出该字符和下标的映射,窗口的大小始终为start到i,如果遍历到某个字符在map中已经有它的映射,那么start的值发生变化,更新为这个字符所对应的map中的下标,即左窗口向右滑动。
代码:
public class Solution{
public int lengthOfLongestSubstring(String s){
if(s==null||s.length()==0)
return 0;
int []map=new int [256];
int start=0;
int len=0;
for(int i=0;i<s.length();i++){
if(map[s.charAt(i)]>start) //大于start的原因是abba这种情况,当b重复时start更新为2,如果这里不是大于start而是大于0,那么访问a的时候会认为a重复,所以必须是大于start。
start=map[s.charAt(i)];
map[s.charAt(i)]=i+1;
len=Math.max(len,(i+1-start));
}
return len;
}
}