A set of template second kill sliding window & leetcode Sliding Window Title Summary

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

Tags: Java Algorithm Double Pointer

Posted by yozyk on Sat, 16 Apr 2022 15:48:13 +0930