Sliding window title template
step1: maintain variables according to the meaning of the question
- And Sum
- Max length_ Len, min length_ len
- Do not repeat hashmap = {}
Step 2: start position and end position of the window
step3: write judgment statements according to conditions and maintain variables in step1
step4: select a method to apply according to the requirements of the topic
- Option 1: the window length is fixed. If the window length reaches the limited length:
- 1. Update relevant variables in step1
- 2. The window left position start moves forward 1 to ensure that the window length remains unchanged when end moves to the right
- Option 2: if the window length is not fixed, the while window condition does not meet:
- 1. Update relevant variables in step1
- 2. Keep moving start until the window conditions are met
Step 5: return the answer
3. Longest substring without repeated characters
Solution: the title mentioned that there is no duplicate string, so the hash table is introduced to maintain the window
Idea 1: key stores the element and value stores the number of occurrences
This method maintains a window by using the number of times the stored key appears:
- end - start + 1 == window.size() indicates that there is no duplicate element in [start,end];
- end - start + 1 >= window. Size() indicates that there are duplicate elements in [start,end], which need to be handled at this time.
public int lengthOfLongestSubstring(String s) {
int start = 0,maxLen = 0;
Map<Character,Integer> window = new HashMap<>();
for (int end = 0; end < s.length(); end++) {
char c = s.charAt(end);
window.put(c,window.getOrDefault(c,0)+1);
/*
1.end - start + 1 == window.size() Description: there is no duplicate element in [start,end]
2.end - start + 1 >= window.size() Description: the repetition method element appears in [start,end]
*/
if (end - start + 1 == window.size()) {
maxLen = Math.max(maxLen,window.size());
}
while (end - start + 1 > window.size()) {
char temp = s.charAt(start);
window.put(temp,window.get(temp) - 1);
if (window.get(temp) == 0) {
window.remove(temp);
}
start++;
}
}
return maxLen;
}
Idea 2: key stores the element and value stores the last subscript of the element (recommended)
This method maintains a window by using the last subscript of the stored key
public int lengthOfLongestSubstring(String s) {
int start = 0,maxLen = 0;
Map<Character,Integer> window = new HashMap<>();
for (int end = 0; end < s.length(); end++) {
char c = s.charAt(end);
if (window.containsKey(c)) {
start = Math.max(window.get(c) + 1,start);
}
maxLen = Math.max(maxLen,end - start + 1);
window.put(c,end);
}
return maxLen;
}
You may wonder why it should be written as start = math max(window.get(c) + 1,start);， Instead of start = window Get (c) + 1. Let's take "abba" as an example and assume start = window get(c) + 1:
- Step 1: first, a: 0 and B: 1 will be stored in the map;
- Step 2: when traversing the second b, start = 1 + 1 = 2;
- Step 3: when traversing to the second a, start = 0 + 1 = 1 (but in step 2, start is already 2, and that's the problem). At this time, if you continue down, maxLen = 3 - 1 + 1 = 3, not the correct answer 2.
If it is start = math max(window.get(c) + 1,start);， So in the third step, start = math Max (1,2) = 2, the result is maxLen = 3 - 2 + 1 = 2, which is the correct result.
1695. Delete the maximum score of the subarray
Idea 1: key stores the element and value stores the number of occurrences
This method maintains a window by using the number of times the stored key appears
public int maximumUniqueSubarray(int[] nums) {
int start = 0,sum = 0,maxVal = Integer.MIN_VALUE;
Map<Integer,Integer> window = new HashMap<>();
for (int end = 0; end < nums.length; end++) {
int temp = nums[end];
sum += temp;
window.put(temp,window.getOrDefault(temp,0) + 1);
if (end - start + 1 == window.size()) {
maxVal = Math.max(maxVal,sum);
}
while (end - start + 1 > window.size()) {
window.put(nums[start],window.get(nums[start]) - 1);
if (window.get(nums[start]) == 0) {
window.remove(nums[start]);
}
sum -= nums[start];
start++;
}
}
return maxVal;
}
Idea 2: key stores the element and value stores the last subscript of the element (recommended)
This method maintains a window by using the last subscript of the stored key
public int maximumUniqueSubarray(int[] nums) {
int start = 0,sum = 0,maxVal = Integer.MIN_VALUE;
Map<Integer,Integer> window = new HashMap<>();
for (int end = 0; end < nums.length; end++) {
if (window.containsKey(nums[end])) {
int temp = start;
start = Math.max(window.get(nums[end]) + 1,start);
while (temp != start) {
sum -= nums[temp++];
}
}
sum += nums[end];
maxVal = Math.max(maxVal,sum);
window.put(nums[end],end);
}
return maxVal;
}
Why write start = math max(window.get(nums[end]) +1,start);， Instead of start = window get(nums[end]) +1;， I've said it before.
438. Find all letter ectopic words in the string (important)
Here, the use of arrays combined with double pointers to maintain a window is very ingenious and needs to be understood.
public List<Integer> findAnagrams(String s, String p) {
int start = 0,end = 0;
List<Integer> result = new ArrayList<>();
int[] count = new int[26];
for (int i = 0; i < p.length(); i++) {
count[p.charAt(i) - 'a']++;
}
while (end < s.length()) {
if (count[s.charAt(end) - 'a'] > 0) {
count[s.charAt(end++) - 'a']--;
if (end - start == p.length()) {
result.add(start);
}
} else {
count[s.charAt(start++) - 'a']++;
}
}
return result;
}
567. Arrangement of strings
The idea of this question is the same as that of the previous one.
public boolean checkInclusion(String s1, String s2) {
int[] count = new int[128];
for (char c : s1.toCharArray()) {
count[c]++;
}
int start = 0,end = 0;
while (end < s2.length()) {
if (count[s2.charAt(end)] > 0) {
count[s2.charAt(end++)]--;
if (end - start == s1.length()) {
return true;
}
} else {
count[s2.charAt(start++)]++;
}
}
return false;
}
Other topics
209. Minimum length subarray
Solution idea: find the minimum length of sum > = target of continuous subarray through sliding window algorithm
public int minSubArrayLen(int target, int[] nums) {
int start = 0,sum = 0,minLen = Integer.MAX_VALUE;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
while (sum >= target) {
minLen = Math.min(end - start + 1,minLen);
sum -= nums[start++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
643. Maximum average number of subarrays I
Solution idea: find the maximum sum of continuous sub arrays with length k through sliding window algorithm, and then divide by K to get the result
public double findMaxAverage(int[] nums, int k) {
int max = Integer.MIN_VALUE;
int sum = 0;
int start = 0;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
if (end - start + 1 == k) {
max = Math.max(sum,max);
sum -= nums[start++];
}
}
return 1.0 * max / k;
}