双指针算法

双指针是最接近数学的基础算法思想，也是最容易理解的思想，其基本原理就是"作差"。

快慢指针

定义两个指针fast和slow，fast比slow快一点，fast在前，slow在后，利用fast和slow的距离差来解决问题。

1 链表倒数第k个元素

利用快慢指针的距离差，快慢指针可以是你在我前面，我们之间的距离差为d，利用这个特点可以解决一些数学问题。

求单链表的倒数第k个元素，链接:{https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/}

因为是单链表，只能从前向后访问，不能从后向前访问，这就比较恶心了，我们可以换个思路，倒数第k个，也就是正数第n-k个，我们来看代码:

public ListNode getKthFromEnd(ListNode head, int k) {
    //统计链表的长度，一共走n步
    int length = 0;
    ListNode temp = head;
    while (temp != null) {
        temp = temp.next;
        length++;
    }

    //找正数第n-k个节点，也就是倒数第k个节点，一共走n-k步
    temp = head;
    int index = length - k;
    while (index > 0) {
        temp = temp.next;
        index--;
    }
    return temp;
}

代码很简单，纯粹使用数学方法解决问题，我们一共走的步长是n+(n-k)，其中n是求链表长度的步数，n-k是找正数第n-k的步数，那么可不可以精简呢，当然可以，我们可以使用快慢指针。

我们定义一个fast指针和一个slow指针，他们都指向头节点，先把fast移动到正数第k个位置，此时slow还在头节点，他们的距离差就是k，然后再一起移动fast和slow，直到fast移动到末尾，此时fast就是所在位置就是n，而slow所在位置就是n-k，也就是正数第n-k个节点，即:倒数第k个节点，妙哉！

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast = head;
    ListNode slow = head;
    // 先把fast移动到第k个节点，走了k步
    while (k > 0) {
        fast = fast.next;
        k--;
    }
    //然后fast和slow一起移动，直到fast到末尾为止，此时走了n-k步
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    //slow所在的就是正数第n-k个节点，也就是倒数第k个节点
    return slow;
}

代码很简单，我们一共走了k+(n-k)，也就是一共走了n步，比第一种方法少走了n-k步，这就是快慢指针的妙处。

2 链表是否有环

利用快慢指针的速度差，快慢指针不一定是你在我前面，还可能是你跑的比我快，比如你的速度是我的2倍。

给定一个链表，判断链表中是否有环，链接{https://leetcode-cn.com/problems/linked-list-cycle/}

我们可以简单粗暴的使用Hash表进行遍历存储，如果有环，那么肯定有一个节点会被遍历两次，此时Hash表检测到有了这个元素，就可以确定链表有环，但是我们有更优的解法，那就是快慢指针，我们知道地球是圆的，如果一个人跑的很快，一个人跑的很慢，那么快的最终还是会和慢的碰面，同理，我们使用快慢指针，快指针一次移动两步，慢指针一次移动一步，如果有环，那么它俩一定会碰面:

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode fast = head;
    ListNode slow = head;
    // 循环终止条件是: fast指针没有移动到终点，因为如果fast移动到终点，说明肯定是无环的
    while (fast != null && fast.next != null) {
        // fast指针每次移动两步
        fast = fast.next.next;
        // slow指针每次移动一步
        slow = slow.next;
        // 如果碰面，说明有环，返回！
        if (fast == slow) return true;
    }
    //无环
    return false;
}

代码的时间复杂度是n，空间复杂度是1，这就是快慢指针的NB之处，因为快慢指针只需要两个指针，它的空间复杂度一定是常数级别的！

碰撞指针

我们上面说的是利用距离差或速度差，都是从同一起点出发，我们还可以从两端出发，利用相遇点来解决一些问题，比如二分查找。

二分查找

链接{https://leetcode-cn.com/problems/binary-search/}

我们利用左右指针，只要左右指针没有相遇，就不断夹逼来缩小范围，直到找到目标或者左右指针相遇为止。

 public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        // 只要左右指针没有相遇，就循环执行
        while (left <= right) {
            // 取中点
            mid = (left + right) / 2;
            // 找到，直接返回!
            if (target == nums[mid]) return mid;
            // 大了，移动左指针
            else if (target > nums[mid]) left = mid + 1;
            // 小了，移动右指针
            else if (target < nums[mid]) right = mid - 1;
        }
        // 没有找到，返回-1
        return -1;
    }

代码很简单，利用左右指针，不断缩小查找范围，直到找到或者左右指针碰撞为止!

夹逼指针

碰撞指针的终结条件是"碰撞"，有时候我们不需要碰撞，只需要界定一个范围即可，但是范围的边界是多少，我们需要用双指针来指定。

盛水最多的容器

链接{https://leetcode-cn.com/problems/container-with-most-water/}，我们需要确定一个矩形，来构造一个容器，保证它的容积是最大的，我们在养成算法思维 (opens new window)讲过这个题目，它用的是夹逼的思想，这里再来看一下(图片来源于leetcode):

我们的目的很简单，就是利用垂直条形和x坐标轴构成一个最大的矩形，我们在两侧定义左右指针，不断移动逼近，来寻找最大的矩形。

public int maxArea(int[] height) {
    //定义左右边界
    int left = 0, right = height.length - 1;
    int temp = 0;
    //终止条件是: 两指针相遇，也就是矩形宽度为0
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left); //求当前面积
        temp = Math.max(temp, area); //取最大的
        // 哪一个高度短就移动哪一个，不断夹逼
        if (height[left] <= height[right]) left++;
        else right--;
    }
    return temp;
}

这个例子我们不断移动指针，夹逼取得最大面积，而夹逼的终止条件就是夹逼的范围为0，也就是right-left=0。还记得高数的夹逼准则吗？

任意的正整数e>0，|N1-N2|>e，因为e是趋近于无穷小的正整数，这里把e表示为0即可，right为N1和N2较大的，left为较小的，那么就是right-left>0，也就是left < right，不就正是我们if里面的的终止条件吗。双指针是最基本的算法思想，大家一定要掌握，并且在日常coding中合理使用，方能得心应手。