大家好，我是梁唐。今天跟大家讲一个很经典也很简单的算法。学了这个算法，可以解决很多问题，更不用说还能跨leetcode了。而很多其他的算法也采用了类似的思想，很有借鉴意义。这个算法的名字叫做两指针算法，英文名称是twopointers。算法原理既然算法叫做二指针，顾名思义，必然与二指针有关。首先申明一下，这里的指针不是传统意义上的指针，可以理解为一个变量或者一个记录位置的标记。我们用两个变量在一个线性表中记录两个位置，并维护这两个位置围成的区间。比如一个区间左边的变量叫l，右边的变量叫r，那么我们维护的就是区间[l,r]。所以两个指针的目的就是保持区间，这也是这个算法的核心目的。因此，该算法的一般应用场景是寻找一个合法的最大区间。当然，实际的问题不会直截了当地告诉你我要求的是合法范围，而是会做各种包装，玩各种花样，给你一些波折。您需要通过分析和理解进入主题。核心诉求。了解了算法的核心目的之后，理解其原理就容易多了。只有一个问题需要解决，就是如何保持区间？我们假设当前的l和r处于合法的位置，我们把[l,r]理解为一个区间，那么l和r的变化就可以看作区间的移动。例如，如果l增加，则可以看作是区间左侧在缩小。我们从[l,r]到[l+1,r]，这意味着从范围的左侧弹出了一个元素。反之，如果r增大，则意味着区间右侧再次扩大，从[l,r]变为[l,r+1]，也就是说区间右侧增加了新的元素。所以我们控制l和r的增加，相当于控制了区间内元素的增减。当我们要移动的时候，可以将r固定的增加一位，也就是给区间增加一个元素。现在加入了新的元素，可能会导致区间的合法性被破坏。我们需要做一些事情来维护区间的合法性，比如我们可以移动左边的l，让元素在区间内弹出，直到恢复合法性。随着r一个一个的移动，我们自然而然的遍历了所有的合法区间，找到另一个最大或者最小的那个就很简单了。这样光看课文可能有点抽象，没关系，我们来看一个具体的例子问题，把刚学的算法应用一下。举个例子，我们以Leetcode的第三题为例。在这道题中，我们需要找到一个字符串中不包含重复字符的最长子串。从表面上看，这是一个弦的问题，估计很多人的思考角度都是围绕着弦展开的。但实际上，我们只需要把我们要找的子串看成是原串上的一个区间，那么这就是一个求最大合法区间的问题。在本题中，合法性是指区间中的字符不同。其实已经很明显了，我们只要应用二指针算法就可以了。首先，我们初始化一个合法的区间。这道题很容易想到合法区间可以是[0,0]。在随后的每一步中，我们将r向右移动一位，即在间隔中插入一个新字符。由于新字符的插入可能会导致区间的有效性被破坏，也就是说重复了某个字符。在这种情况下，我们移动l指针并弹出范围内的元素，直到范围再次合法。为了判断区间的有效性是否恢复，我们需要用一个map来存储区间中每个元素的个数。当新插入的字符数大于1时，说明合法性已经被破坏，直到这个数回到1。只看代码的描述，可能有些抽象，没关系，我们结合代码来解释。classSolution{public:intlengthOfLongestSubstring(strings){map
