[algorithm learning] - sliding window algorithm (javascript)

Sliding window algorithm:

Literally, everyone has seen the window and can open and close the window ×)
The window of the sliding window algorithm here is divided into fixed and unfixed. The fixed window is the kind of window seen in life. Imagine a large window, and then the sliding screen window. The screen window here is a fixed sliding window. If it is not fixed, you need to imagine that the screen window is retractable.
Just look for a picture on the Internet, you can feel it:

The back large window is the object to be traversed. The screen window is divided into left border and right border, which is used to find qualified target objects in the large window. Note: for fixed windows, it is not necessary to use the left border, because for fixed windows, if the fixed size is k, directly subtract K from the right border to equal the left border.

Take a look at a sliding window algorithm to feel (fixed window): Language: JavaScript
1. Self created problem (very simple, you can play): given a group of arrays, traverse the array, count every three as a substring, and calculate the sum of substrings of each combination,
Advanced: find the maximum value after calculating the sum of each combined substring.
Input: [- 3, 3, 5, 1, 3, 7, 4]
Output: [5, 9, 9, 11, 14]
Advanced output: 14
Explanation: ① - 3 + 3 + 5 = 5 ② 3 + 5 + 1 = 9 ③ 5 + 1 + 3 = 9 ④ 1 + 3 + 7 = 11 ⑤ 3 + 7 + 4 = 14
The following shows the stupidest method hhh (think about the optimization scheme later):

function temp(s) {
  let left = 0,right = 2; // Defines the left and right borders of a sliding window
  let sumArr = [];  // The sum of each slide is put into a new array
  let n = s.length;    // The length of the array is assigned to a new variable
  if (n <= 2) { //Because the fixed window is 3, if the number of values in the array is less than 3, there is no need to continue
   return s;  // Return array directly
  }
  while (right < n) { //Traversal condition: stop traversal when the right border is greater than n and control the number of times
    let sum = 0;  // Sum is used to record the sum of each group of substrings. Because it needs to be reused, it should be set to 0
    for (let i = left; i <= right; i++) { // The two-level loop is used to traverse each [left,right] substring
      sum += s[i];  //Sum of substrings of every three
    }
    sumArr.push(sum); // Get a set of sums and put them in the new array
    right++;  // After calculating a set of substrings, the window begins to slide to the right
    left++;
  }
  const max = Math.max(...sumArr); // Gets the maximum value of a set of arrays
  return sumArr; //Advanced: find the maximum number in the array: math max(…sumArr);
  }
}

Knowledge points:

    ① length()Method returns the length of an array or string
    ② push() Method adds one or more elements to the end of the array and returns the new length of the array
    ③ Math.max() Function returns the maximum value in a set of numbers

Simply list the knowledge points. You can learn from MDN.

2. The title of Li Kou net = the longest substring without repeated characters (link here, you can do it if you are interested):
https://leetcode-cn.com/probl...
Given a string s, please find the length of the longest substring that does not contain duplicate characters.
Input: s = "pwwkew"
Output: 3
Explanation: because the longest substring without repeated characters is "wke", its length is 3.

 Please note that your answer must be the length of the substring,"pwke" Is a subsequence, not a substring.

Here are three simple ways to write:
Method 1: set / map (almost, use set, map is not necessary)

function temp(s) {
  let n = s.length;
  let set = new Set();  // Define a set
  let left = 0, right = 0, maxLen = 0; // Left and right borders, maximum
  if (n < =1) {  // If s is less than or equal to 1, there is no need to judge and directly output the length
    return n;
  }
  while (right < n) {
    if (!set.has(s[right])) {  // Judge whether the set contains the elements in s
      set.add(s[right]);  // Add set if not included
      maxLen = Math.max(maxLen, right - left + 1);  //Then calculate the length of the longest substring without repetition. Because it is a window, the length is right-left+1 (right border – left border + 1)
      right++;   // When there are no duplicate elements, the right border continues to slide to the right
    } else {
      set.delete(s[left]);  // If there are duplicate values in set, delete them from the left border
      left++;  // Slide left border
    }
  }
  return maxLen;
};

Knowledge points:

  ① newly build set: let set = new Set();be careful set The elements in the are not repeated 
  ② set Methods in: has,add,delete etc.
  ③ Math.max() Function returns the maximum value in a set of numbers

Illustration (crude version):

Illustration (advanced version):

Method 2: array method (this is equivalent to fixing windows, one at a time)

function temp (s) {
  let arr = [],max = 0;
  if (s.length <=1) {
    return s.length;
  }
  for (let i = 0; i < s.length; i++) {
    let index = arr.indexOf(s[i]);  // Check whether the array contains the elements in s
    if (index !== -1) {    // If the index is equal to - 1, it is not included. It is judged to be included here
      arr.splice(0, index + 1);  // Delete the duplicate values from 0 to in the array
    } else {    
      arr.push(s[i]); //Or arr.push(s.charAt(i))// If there are no duplicates, put the elements into the array
      max = Math.max(max, arr.length);  // Judge length
    }
  }
  return max;
};

Knowledge points:

    ① indexOf: Check whether the array contains an element, return its subscript if it exists, and return if it does not exist-1
    ② splice(start,count,item): Delete the elements in the array, starting from 0 start Start deletion count Elements, item Optional. See for specific usage MDN. 
    ③ push(): Adds an element to the end of the array
    ④ charAt(index): Returns the value of the specified coordinate from a string

Illustration: (orange is the input array and blue is the new array)

Method 3: subscript method

function temp(s) {
  let index = 0,max = 0;
  if (s.length <= 1) {
    return s.length;
  }
  for (let let = 0, right = 0; right < s.length; right++) { // Traversal string
    index = s.substring(left, right).indexOf(s[right]); //  Determine whether there are duplicate elements in the string
    if (index !== -1) {
      left = left + index + 1; // If there is a repeating element, slide the window and directly jump to the next index of the repeating element, left + repeating element subscript + 1
    } else { //No duplicate elements, compare max and right left + 1
      max = Math.max(max, right - left + 1);
    }
  }
  return max;
}

Knowledge points:

① substring(start,end): Method in string,Intercept from[start,end)Substring of
 be careful: index That step, indexOf Yes substring Based on, so the returned index is also from substring Starts from the string of. This affects left=left+index+1 That step. If there are duplicate elements, just slide the left border directly to the next index of the duplicate element.

Illustration:


Reference article:
https://leetcode-cn.com/probl...
I refer to the above articles and my own understanding when doing the title. I hope to correct some mistakes. For details of the knowledge points, please refer to the official documents of MDN. Let's put some here first (String, Array and Math methods)
[String]https://developer.mozilla.org...

[Math]https://developer.mozilla.org...

[Array]https://developer.mozilla.org...

Keywords: Javascript Algorithm

Added by mgoerz on Thu, 13 Jan 2022 14:26:19 +0200