題目: 給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度巢音。
**示例**
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
解題思路
使用滑動(dòng)窗口的思想來(lái)解決這個(gè)問題如失，窗口的邊界可以理解為下標(biāo),i表示字符串的左邊界，j表示字符串的右邊界送粱。假設(shè)在數(shù)組(i,j)的范圍內(nèi)發(fā)現(xiàn)str[i]=str[j]褪贵。那么只需要將i的值賦值為j+1即可。然后再進(jìn)行以上的判斷抗俄。這里我們利用HashMap脆丁。
import java.util.HashMap;
/*
* @author: mario
* @date: 2019/1/5
* 無(wú)重復(fù)字符的最長(zhǎng)子串
* **/
public class Problem03 {
public int lengthOfLongestSubstring(String str) {
if(str.length() == 0 || str == null){
return 0;
}
int len = str.length(), ans = 0;
HashMap<Character, Integer> map = new HashMap<>();
for(int j = 0, i = 0; j < len; j++){
if(map.containsKey(str.charAt(j))){
i = Math.max(map.get(str.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(str.charAt(j), j+1);
}
return ans;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Problem03 pb = new Problem03();
String str = "abcabcbb";
int result = pb.lengthOfLongestSubstring(str);
System.out.println("result:"+result);
}
}
LeetCode題目地址: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
