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; }