Popular science: What is sliding window algorithm

The sliding problem contains a sliding window, which is a sublist running on a large array, a collection of underlying elements.

Suppose there is an array [a, b, C, d, e, f, g, h] and a sliding window of size 3 sliding on it, then:

[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]
Copy the code

In general, this window is used to slide the array within the legal range and record some useful data dynamically. In many cases, it can greatly improve the efficiency of the algorithm.

1. Maximum sliding window value

The title comes from LeetCode problem No. 239: Sliding window maxima. So far, the pass rate is 40.5%.

Topic describes

Given an array numS, there is a sliding window of size K that moves from the leftmost of the array to the rightmost of the array. You can only see the numbers in the sliding window K. The sliding window moves only one bit to the right at a time.

Returns the maximum sliding window value.

Example:

Enter: nums = [1.3, -1, -3.5.3.6.7], and k =3Output:3.3.5.5.6.7] the maximum position of the sliding window --------------- ----- [1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
Copy the code

title

Use a double-ended queue, store the position of the element in the array in the queue, and maintain strict decrement of the queue, that is, maintain the first element of the queue is the largest **, when traversing a new element, if there is a smaller element in the queue, it will be removed from the queue to ensure the queue decrement. When the difference between the positions of queue elements is greater than k, the first queue element is removed.

Added: What is a Dqueue?

A Deque means “double ended queue”, that is, a double-ended queue, which has the nature of a queue and a stack of data structures. As the name implies, it is a queue that supports insert and delete operations at both the front and back ends.

Deques inherit from queues, and their direct implementations are ArrayDeques, LinkedLists, and so on.

Animation description

Code implementation

class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
        // The array is not empty and k > 0. However, the test case still has nums = [], k = 0, so we have to add this judgment
        if (nums == null || nums.length < k || k == 0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        // Double-endian queue
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // Add elements to the tail and make sure the left elements are larger than the tail
            while(! deque.isEmpty() && nums[deque.getLast()] < nums[i]) { deque.removeLast(); } deque.addLast(i);// Remove the element in the header
            if (deque.getFirst() == i - k) {
                deque.removeFirst();
            }
            // Output the result
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.getFirst()]; }}returnres; }}Copy the code

2. The oldest string without repeating characters

The title comes from question No. 3 on LeetCode: the oldest string without repeating characters. The question is Medium in difficulty and the current pass rate is 29.0%.

Topic describes

Given a string, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input:"abcabcbb"Output:3Because the oldest string without repeating characters is"abc", so its length is3.Copy the code

title

Create a 256-bit integer array freg to map characters to their locations.

Maintain a sliding window, the window is not repeated characters, to maximize the size of the window, the window keeps sliding right.

  • (1) If the current traversal character never appears, then directly expand the right boundary;
  • (2) If the current traversal character appears, then narrow the window (the left index moves to the right), and then continue to observe the current traversal character;
  • (3) Repeat (1) and (2) until the left index can no longer be moved;
  • (4) Maintain a result RES, update the result RES with the size of the window every time, and finally return RES to obtain the result.

Animation description

Code implementation

// Slide window
O(len(s))
O(len(charset))
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};
        int l = 0, r = - 1; // Slide window is s[l...r]
        int res = 0;
        // complete loop from l == 0; R == -1, the empty window starts
        // to l == s.size(); R == s.size()-1 This empty window closes
        // Change the window gradually in each loop, maintain freQ, and record if a new optimal value is found in the current window
        while(l < s.size()){
            if(r + 1 < s.size() && freq[s[r+1= =]]0){
                r++;
                freq[s[r]]++;
            }else {   / / r is | | freq [s] [r + 1] = = 1
                freq[s[l]]--;
                l++;
            }
            res = max(res, r-l+1);
        }
        returnres; }};Copy the code

3. Repeated element II exists

The title comes from problem no. 219 on LeetCode: there are duplicate elements II. The difficulty of the questions is Easy and the current pass rate is 33.9%.

Topic describes

Given an integer array and an integer k, determine whether there are two different indexes I and j in the array such that nums [I] = nums [j] and the absolute value of the difference between I and j is at most K.

Example 1:

Input: nums = [1,2,3,1], k = 3true
Copy the code

Example 2:

Input: nums = [1,0,1,1], k = 1true
Copy the code

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2false
Copy the code

title

Use sliding Windows and lookup tables to solve.

  • Setting up the lookup tablerecord, which is used to save the elements inserted at each iteration,recordThe maximum length of isk
  • Through the arraynumsAnd each time I go through itrecordFinds if the same element exists and returns if sotrue, the traversal is complete
  • If this traversal is atrecordIf not found, insert the element torecord, and then viewrecordIs the length ofk + 1
  • If at this timerecordIs the length ofk + 1The cutrecordElement, whose value isnums[i - k]
  • If I iterate through the entire arraynumsReturns if not foundfalse

Animation description

Code implementation

// Time complexity: O(n)
// Space complexity: O(k)
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size() <= 1)  return false;
        if(k <= 0)  return false;
        unordered_set<int> record;
        for(int i = 0 ; i < nums.size() ; i ++){
            if(record.find(nums[i]) ! = record.end()){return true;
            }
            record.insert(nums[i]);
            // Keep a maximum of k elements in the record
            // Because a new element will be added in the next loop, k+1 elements will be considered in total
            if(record.size() == k + 1){ record.erase(nums[i - k]); }}return false; }};Copy the code

4. The smallest subarray

The title comes from problem no. 209 on LeetCode: Smallest subarray. The question is Medium and currently has a pass rate of 37.7%.

Topic describes

Given an array of n positive integers and a positive integer **s, find the smallest contiguous subarray in the array whose sum ≥ s. ** Returns 0 if no contiguous subarray exists.

Example:

Enter: s =7, nums = [2.3.1.2.4.3] output:2Explanation: Subarray [4.3] is the smallest continuous subarray in this condition.Copy the code

title

Define two Pointers, left and right, to record the left and right boundaries of the subarray.

  • (1) Move right until the sum of the subarray is greater than or equal to the given value or right reaches the end of the array;
  • (2) Update the shortest distance, move the left image one bit to the right, and subtract the removed value from sum;
  • (3) Repeat steps (1) and (2) until right reaches the end and left reaches the critical position

Animation description

Set the length of the slide window to 0 at the left end of the number line.

1. R at the right end of the sliding window starts to move until the interval meets the given condition, that is, the sum is greater than 7. At this point, it stops at the third element 2, and the current optimal length is 4

2. The left end L of the sliding window starts to move, reduces the size of the sliding window, and stops at the first element 3. At this time, the interval sum is 6, so that the interval sum does not meet the given condition (no more than 7 at this time).

3. R at the right end of the sliding window continues to move and stops at the fourth element 4, which is equal to 10, but the optimal length is still 4

Code implementation

// The idea of sliding Windows
// Time complexity: O(n)
// Space complexity: O(1)
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int l= 0,r = -1;    // nums[l...r] is our sliding window
        int sum = 0;
        int result = nums.length + 1;
        while (l < nums.length){ // If the left edge of the window is in the range of the array, the loop continues

            if( r+1 <nums.length && sum < s){
                r++;
                sum += nums[r];
            }else { // sum >= s
                sum -= nums[l];
                l++;
            }

            if(sum >= s){
                result = (r-l+1) < result ? (r-l+1) : result ; }}if(result==nums.length+1) {return 0;
        }
        returnresult; }}Copy the code

Personal website: www.cxyxiaowu.com

Individual public number: five minutes to learn the algorithm