Topic describes

Their thinking

  • In this case, double Pointers and hash tables are used to solve the problem.
  • The maximum value is constantly updated.
  • The right pointer moves to the last element of the string and the loop ends.
  • The body of the loop determines whether the element pointed to by the right pointer is present in the hash table. If so, the corresponding value +1 is assigned; otherwise, the value 1 is assigned.
  • Hash table existence is the movement of the pointer on the left, in order to assist us when right pointer elements, the number of occurrences of greater than 2, at this time that repeated, we will constantly moves the pointer left, until the right pointer repeat this element does not repeat, moves the pointer left before the left pointer to the element the hash value of 1, to prevent the occurrence of the same element behind
  • Finally, the right pointer moves right, and the larger values of res and right-left are assigned to res constantly compared.

The problem solving code

var lengthOfLongestSubstring = function(s) {
    // In this case, the sliding window + double pointer method is adopted
    // Define the left pointer
    let left = 0;
    // Define the right pointer
    let right = 0;
    // Define the maximum value
    let res = 0;
    // Define sliding window (hash table)
    let window = new Map(a);// The loop ends when the right pointer goes to the far right
    while (right < s.length) {
        // Determine if the element to which the right pointer points is in the hash table, +1 if it is in the hash table, +1 if it is not
        if (window.has(s[right])) {
            window.set(s[right],window.get(s[right]) + 1);
        } else {
            window.set(s[right],1);
        }
        // Determine if there is a duplicate of the element to which the right pointer points
        while (window.get(s[right]) > 1) {
            // The value of the left pointer in the hash table is -1, and the left pointer moves to the right
            // The fundamental reason for moving to the right after -1 is to prevent the left element from repeating itself
            window.set(s[left],window.get(s[left]) -1);
            left++;
        }
        // Move the pointer right to update the maximum value
        right++;
        res = Math.max(res,right - left);
    }

    return res;
};
Copy the code

Refer to the link

Finger Offer – longest substring without repeating characters (JS implementation)

Conclusion (this topic gives us the enlightenment of thinking)

  • Learn to maximize by constantly updating.
  • Learn how to solve problems with a hash table and a double pointer.