preface

This article has included making https://github.com/ponkans/F2E (a big monster is finishing the front-end knowledge skill tree), welcome to Star, continuously updated 💧

To tell you the truth, writing the algorithm for the first time strange, a little nervous, after all, is a math how also can not lattice of small dishes.

The fourth from the bottom of the class at the end of the first semester, puyi, poor grades of students hammer ~

Before writing, I was thinking how to write the algorithm more interesting, like the high number class in college, to tell the truth, the teacher is really boring.

It would be hard to hear if it weren’t for the so-called academic rules.

Let M(x0,y0,z0) be the known point on the plane, n=(A,B,C) be the normal vector, M(x,y,z) be any point on the plane, then the French equation of the point on the plane is XXXX, listen to listen to fall asleep… (Teacher, I can’t carry!!)

So, Geek will try to make it as interesting as possible, so that you can almost remember the idea of the algorithm after reading it.

Given a string, find the length of the longest string that does not contain repeated characters.

Just a quick explanation.

For example, given the string “propyl to water freak to water freak”

The first step is to find substrings in the string that do not contain repeating characters

  • c
  • C pick
  • C pick up water
  • C pick monster
  • The creature by

The second step is to calculate the length of each substring and take the maximum value.

  • In this case the maximum is obviously 4, so the answer is 4

Ok, finish the example, in fact, it is easy to find, the core is the first step, find the substring does not contain repeated characters.

That exactly how to find it, in order to facilitate the first time to see the algorithm of small partners to understand, I drew a few pictures, we do not understand after reading, plus wechat scolded me cheating and playing with women’s feelings of the man!

Find two guns and start pointing at the first character.

We found our first non-repeating substring, c.

Then hold the red gun still and move the green one step back.

At this time, the characters are repeated between the two guns, find the same position as the green gun, and move the red gun to the last position of the repeated position, so this time becomes the following.

So we find the second non-repeating string, which is also c, just like the first one.

Don’t panic. Let’s keep moving the green guns.

Because, in the process of moving, there has been no repetition between the red and green gun, we found the non-repeating sub-string “C connect”, “C connect water”, “C connect water monster”

No rush, no rush, no more, then move the green gun (the green gun is in last place, over)

It can be found that when we move the green gun to “connect”, repeated “connect” appears in the sub-string between red and green, so we still repeat the previous idea:

  • Find the position of the repeated character “accept”
  • Move the red gun to the next position, water
  • Get a non-repeating substring between red and green.

Thus, when our green gun moves to the last digit, our search is over, and we have found all the non-repeating substrings.

In fact, the red gun, the green gun, in other words, is the left and right pointer, moving the red and green gun, is moving the left and right pointer, and the window between the two Pointers is what we want.

It’s very similar to the thing we drag to capture the progress of the video when we cut the video.

This idea of solving problems is what we often call sliding Windows.

Once you understand the idea, writing code is actually relatively easy.

Let’s go to LeetCode. I have written some boundary cases in the comments. Remove comments about 10 lines of code, I suggest you do it for the first time, trust me, you will be able to write.

Maybe you can start your LeetCode algorithm journey 💗~

summary

Sliding window problem, in fact, is to figure out the left and right sliding boundary is what [ate a fruit], such as the above problem when the left window contraction is the key.

I’ve opened a series of columns on algorithms, and I’ll write about algorithms in the future. In the near future, I think algorithms will focus on sliding Windows.

A National Day summary mentioned some technology, the recent probability is the rhythm of the article

  • Redux source code, design ideas
  • Promise, Generator, async await source code (after all, work is used frequently, need to see)
  • The new company stack is called React.
  • algorithm

I am a water monster, an ordinary programmer. Thank you for your attention and 3 company 💕😊

Contact me/public number

Wechat search “water monster” or scan the qr code below reply “add group”, I will pull you into the technical communication group. Honestly, in this group, even if you don’t talk, just reading the chat is a kind of growth. (Ali technical experts, aobing authors, Java3y, mogujie senior front end, Ant Financial security experts, all the big names).

The water monster will also be regular original, regular with small partners to exchange experience or help read the resume. Add attention, don’t get lost, have a chance to run together 🏃 ↓↓↓