Longest Substring Without Repeating Characters, Leetcode 解题笔记

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.

这道题很“戏剧化”, 我做完后一直提示超时,通不过,后来对比10个月前成功提交的代码,完全找不到错误,于是干脆copy之前正确的代码再次提交,发现还是超时。看来leetcode对这道题的时限要求做过更改。

初看这道题,第一反应是遍历,利用HashMap记录已出现的字符,每次遇到重复记录当前最大长度并且更新HashMap, 需要注意的是题目要求找到最大长度,所以要记录每次遍历的开始位置,而每次的开始位置是上一个重复字符的位置+1, 例如”abcdefbg”这个字符串,当发现第二个b与第一个b重复后,下一次遍历的开始位置应从’c’开始。

利用HashMap的代码如下:

public static int lengthOfLongestSubstring(String s) {
 
	char[] arr = s.toCharArray();
	int pre = 0;
 
	HashMap<Character, Integer> map = new HashMap<Character, Integer>();
 
	for (int i = 0; i < arr.length; i++) {
		if (!map.containsKey(arr[i])) {
			map.put(arr[i], i);
		} else {
			pre = pre > map.size() ? pre : map.size();
			i = map.get(arr[i]);
			map.clear();
		}
	}
 
	return Math.max(pre, map.size());
}

因为上面的代码以前可以通过,而现在不能,这里附上另一代码,思路基本相同,唯一的区别是不用HashMap,而是用一个flag array来存储已出现的字符。此代码可以通过。

public int lengthOfLongestSubstring(String s) {
	boolean[] flag = new boolean[256];
 
	int result = 0;
	int j = 0;
	char[] arr = s.toCharArray();
 
	for (int i = 0; i < arr.length; i++) {
		char c = arr[i];
		if (flag[c]) {
			result = Math.max(result, i - j);
			for (int k = j; k < i; k++) {
				if (arr[k] == c) {
					j = k + 1;
					break;
				}
				flag[arr[k]] = false;
			}	
		} else {
			flag[c] = true;
		}
	}
 
	result=Math.max(arr.length-j,result);
 
	return result;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s