双指针学习笔记

在数组问题中，有一类非常常见的技巧——双指针。顾名思义是用两个指针（变量）来记录一些关键信息。那么首先我们需要了解一下，那些关键信息是什么？

本文为算法学习的一篇笔记，观看本文可能需要一些前置知识 chaiquan_love

循环不变量

其实那些关键信息绝大部分是循环不变量。「循环不变量」是指我们在编写代码的过程中，要一直循序不变的性质，这样的性质是根据要解决的问题，由我们自己定义的。他还需要保证在解题过程中的三个阶段内的性质不变，这样才能作为我们解题的基础。这三个阶段分别是

初始化
循环遍历
结束

举个例子： 27. 移除元素

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let len = nums.length;
    let i = 0;

    for(let j = 0; j < len; j ++)
        if(nums[j] != val)
            nums[i++] = nums[j];

    return i;
};

这里，我定义区间$[0,i]$为我的移除元素后的数组边界，那么此时他就是我的第一个指针（即循环不变量）。而j则是我正常遍历的第二个指针。

那么初始化时，我的i作为移除元素后的数组边界，此时应该是长度为0的（因为还没有开始解题）

在使用第二个指针遍历数组期间，我也根据区间$[0,i]$的性质与逻辑去编写相应的代码。这里就是当遍历到的元素不为需要移除的元素的时候，就将当前元素赋值给指针i指向的位置，时刻保持着他的性质都是「移除元素后的数组边界」

在结尾时，因为我在遍历期间始终保持着指针i的性质，那我很轻易就可以知道，我的需要的答案就是此时的i了。

最后稍微总结一下。循环不变量本身的意义就在于你怎么去定义它的，你想让他记录什么，那么在初始化的时候就根据相应的逻辑进行初始化，在遍历的时候也根据相应的逻辑进行操作。最后得到的，就是你想要的东西。

留个小问题：283. 移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let len = nums.length,
        left = 0,
        right = 0;

    while(right < len) {
        if(nums[right]) {
            let temp = nums[left];
            nums[left++] = nums[right];
            nums[right] = temp;
        }
        right++;
    }
};

这里我的left指针维护的是个什么呢？

答案

实际上是数组非零部分的边界，也就是说$[0, left)$区间内的都是原数组中的非零部分，而$[left, len-1]$则是数组全部的0。

双指针

其实说完循环不变量，双指针的精髓也差不多介绍完了。其实双指针是非常灵活的一种技巧，每一题的双指针的含义，都是对题目进行充分理解后总结出的。但是也有些规律，例如上面的移动零和移除元素两道题，是通过某一指针去维护一个内容区间，而有一些又不是如此。我凭借我微乎其微的写题经验稍微总结了一下，大概有以下几种

区间维护（例题：283. 移动零 | 27. 移除元素 75. 颜色分类）
类似于动态规划的双指针（例题：167. 两数之和 II - 输入有序数组 | 11. 盛最多水的容器）
快慢指针（例题：19. 删除链表的倒数第 N 个结点 | 876. 链表的中间结点）

第一种刚刚已经说过了，接下来再介绍一下第二种：类似DP的双指针。

以11. 盛最多水的容器作为例题

/**
 * @param {number[]} h
 * @return {number}
 */
var maxArea = function(h) {
    let len = h.length,
        left = 0,
        right = len - 1,
        result = 0;
    
    while(left < right) {
        result = Math.min(h[left], h[right]) * (right - left) > result ? Math.min(h[left], h[right]) * (right - left) : result;
        if(h[left] > h[right]) right--;
        else left++;
    }

    return result;
};

这里的双指针的作用是作为边界从两侧同时遍历数组，动态地去查找最大容量。基本逻辑是这样子的：双指针left和right，分别从区间两侧逼近，每次计算当前两个指针所围成的容器大小与之前的最大值进行比较，比之前的最大值还大则保存。接下来就是较小的那一边移动直到两指针相交。最后的结果就是我们记录的最大值。

167. 两数之和 II - 输入有序数组也是类似的逻辑。

最后一种快慢指针，也是一种非常巧妙的技巧。两个指针根据含义，设置不同的移动步长。例如例题876. 链表的中间结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* p1 = head, *p2 = head->next;
        
        while(p2 != nullptr) {
            p2 = p2->next;
            p1 = p1->next;
            if(p2 == nullptr) return p1;
            p2 = p2->next;
        }
        
        return p1;
    }
};

要求寻找链表的中间节点，那么此时的我的快指针的步长就应该是我慢指针步长的两倍，这样子当我的快指针到链尾时，我的慢指针就刚刚好到了中间节点。