Sliding Window

Share on:

Sliding Window Overview

Longest Substring with At Most K Distinct Characters 这个问题有一个简便的思路是,用一个(key, rightPosition)的HashMap来替代(key, frequency)的HashMap.

Subarrays with K Different Integers 方便求at most K different integer, 所以我们可以采用prefix sum的思路来处理。注意 right - left = 当前最多依然使用的是prefix sum

Code

 1	int count = map.size();  //record element
 2	int left = 0, right = 0;
 3	List<Integer> res = new ArrayList<>();
 4	while (right < s.length()){
 5		char ch = s.charAt(right);
 6		if (map.containsKey(ch)){
 7	    	map.put(ch, map.get(ch) - 1);
 8	    	if (map.get(ch) == 0) count--;
 9		}
10		right++;
11		while (count == 0){
12	    	//condition to record results
13	    	if (right - left == p.length()){
14	        	res.add(left);
15	    	}
16	    	ch = s.charAt(left);
17	    	if (map.containsKey(ch)){
18	        	map.put(ch, map.get(ch) + 1);
19	        	if (map.get(ch) == 1) count++;
20	    	}
21	    	left++;
22		}
23	}