Posted Dev / Algorithm3 minutes read (About 445 words) visits
Sliding Window
Examples
3-无重复字符的最长子串
Time Complexity $O(n)$. The left and right pointers do not decrease and each character will be added and removed at most once.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
import java.util.HashSet; import java.util.Set;
classSolution { publicintlengthOfLongestSubstring(String s) { Set<Character> substrWindow = newHashSet<Character>(); // set to store the characters in the current substring intres=0; for (intleft=0, right = 0; right < s.length(); right++) { charch= s.charAt(right); substrWindow.add(ch); res = Math.max(res, right - left + 1); while (substrWindow.contains(ch)) { // shrink left bound substrWindow.remove(s.charAt(left++)); } } return res; } }