[LeetCode]Longest Substring Without Repeating Characters

仍然是双指针是的方法，这里我们只需要维护一个set来判断有没有重复的character就可以，左指针的移动策略如下：

• 如果right指向的字符不在set里，更新set，看当前substring是不是更长，更长就把结果设为当前substring
• 如果right指向的字符在set里，左移left直到移除和当前right指向的那个字符一样的字符为止，更新set，看当前substring是不是更长，更长就把结果设为当前substring

时间复杂度是O(n)，代码如下：

	public class Solution {
	public int lengthOfLongestSubstring(String s) {
	if (s == null)
	return 0;
	int len = s.length();
	HashSet<Character> set = new HashSet<Character>();
	int left = 0, max = 0;
	for (int right = 0; right < len; right++) {
	char curr = s.charAt(right);
	if (set.contains(curr)) {
	char temp;
	do {
	temp = s.charAt(left);
	set.remove(temp);
	left++;
	}while(temp != curr);
	}
	set.add(curr);
	if (right - left + 1 > max)
	max = right - left + 1;
	}
	return max;
	}
	}

view raw Longest Substring Without Repeating Characters.java hosted with ❤ by GitHub