用左右两个指针,右指针往右移同时把char加进hashset里面,当hashset出现重复时,计算当前长度,移动左指针,一直到左指针指向重复的元素,把经过的元素移除hashset。重复以上过程。
public class Solution { //Time: O(n) Space: O(n) public int lengthOfLongestSubstring(String s) { if (s.length() <= 1) { return s.length(); } HashSet<Character> set = new HashSet<Character>(); int left = 0; int i = 0; int max = 0; for (; i < s.length(); i++) { if (!set.contains(s.charAt(i))) { set.add(s.charAt(i)); } else { max = Math.max(max, i - left); while (left < i && s.charAt(left) != s.charAt(i)) { set.remove(s.charAt(left)); left++; } left++; } } max = Math.max(max, i - left); return max; } }
No comments:
Post a Comment