Topic describes

Their thinking

  • In this case, hash table + sliding window idea
  • The hash table is used to store the number of occurrences of each character, and when a single character occurs twice, it is used to help us move the sliding window
  • First, we define a left and right pointer. The left and right Pointers start at 0, and the right pointer keeps moving to the right as a condition for judging the loop. When the right pointer moves to the length of the string, the loop ends.
  • Specific process to see notes, notes are very detailed

Solution code (simulated queue)

var lengthOfLongestSubstring = function (s) {
    / /! This problem is solved by sliding window + hash table
    // Define the slider window, which is a hash table, the key of the hash table: single character value: the number of occurrences of the character
    const window = new Map(a);// Define the left pointer
    let left = 0;
    // Define the right pointer
    let right = 0;
    // Define the maximum length of a non-repeating substring
    let res = 0;
    // When the right pointer is smaller than the length of the string, it is a condition to enter the loop
    while (right < s.length) {

        // Since we are moving the right pointer, we need to check whether the hash table contains elements to which the right pointer points
        if (window.has(s[right])) {
            window.set(s[right],window.get(s[right]) + 1);
        } else {
            window.set(s[right],1);
        }
        // Determine if the element to which the right pointer points is duplicated
        while (window.get(s[right]) > 1) {
            // The number of occurrences of the left pointer to the element is -1, then the left pointer moves to the right until the element repeated is no longer repeated
            window.set(s[left],window.get(s[left]) - 1);
            left++;
        }
        right++;
        res = Math.max(res,right - left);
    }
    return res;
};
Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Lesson 1: Learn to use sliding Windows + hash tables
  • Lesson 2: Learn to use double Pointers
  • Lesson 3: Learn to maximize by updating