算法基础–双指针

本文介绍: 前面已经写了两篇关于算法方面的文章，这几天想了下，决定把这个算法整理成一个系列，除了是帮助自己巩固算法知识外，还能够把自己总结的每种算法的套路保存下来并分享给大家，这样以后即使是哪天想要重拾起来，也是能够根据这些算法套路快速重拾。那么好，这道题可能很多小伙伴会说太简单了，如果双指针只有这水平，那大家都可以洗洗睡了，还在算法的题海里面挣扎个什么劲。但是现在嘛，首尾指针给它安排上，两个指针指向的数值，比较小的往对方靠拢（为什么这样自己去想想），记录一个最大值，不断刷新满足条件的值，直到两个指针相遇，结束。

前面已经写了两篇关于算法方面的文章，这几天想了下，决定把这个算法整理成一个系列，除了是帮助自己巩固算法知识外，还能够把自己总结的每种算法的套路保存下来并分享给大家，这样以后即使是哪天想要重拾起来，也是能够根据这些算法套路快速重拾。

我想了下，算法这块主要分为五大块，分别是双指针、栈（单调栈）、深度优先搜索（DFS）、广度优先搜索（BFS）、动态规划。今天就从双指针开始，从双指针算法概述、套路模板，以及根据这个模板，进行几道算法题的讲解，从简单到难，让小白也能由浅入深了解这个算法。

双指针，是一种通过设置两个指针不断进行单向移动来解决问题的算法思想。一般包含两种形式：一、两个指针指向同一个序列。二、两个指针分别指向不同的序列。指向同一序列的比较常见，代表有快慢指针，首尾指针，固定间距指针等。指向不同序列的双指针代表有归并排序这种，需要合并时用双指针或者多指针。

说得那么概念，可能大家反而没什么感觉，不就是两个指针，根据一定的条件触发两个指针的移动，然后把满足一定条件的结果作为最终结果嘛。但是，下面，来点干货，套路模板来了，不管什么样的算法题，只要是双指针的题目，记住下面这个套路模板，然后稍微调整下边界值，就可以直接往上套了，以不变应万变：

public Type twoPoints() {
        int left;
        int right;
        Type result
        while (满足继续循环条件) {
            if (满足左指针移动) {
                left++;
				if(满足更新result条件) 更新result;
            } else {
                right++/right--;
				if(满足更新result条件呢) 更新result;
            }
        }
        return result;
    }

那么好，看到上面这个模板我就想立马给各种类型的双指针场景给安排上，让我试一试这把刀锋不锋利，首先来第一种，快慢指针，我在leetcode上一下子就找到了，看看这题目怎么描述的：

3. 无重复字符的最长子串

不知道是不是刷题刷多了，看到题就会大概猜到这道题要用什么算法，我相信很多人都有这种感觉，一看到这题目，就知道这肯定是双指针，并且是快慢指针就能搞定。那么好，我们直接套模板，把代码写出来：

public int lengthOfLongestSubstring(String s) {
        Set<Character&gt; containString = new HashSet<&gt;();// 子串中包含的所有字符
        char[] sChar = s.toCharArray();
        int left = 0;
        int right = 0;
        int max = 0;
        while (right < sChar.length) {// 右指针走到最右端的时候，循环就可以结束了
            if (!containString.contains(sChar[right])) {// 满足右指针继续右移的条件
                containString.add(sChar[right]);
                max = max > right - left + 1 ? max : right - left + 1;
                right++;
            } else {// 满足左指针右移的条件
                while (containString.contains(sChar[right])) {
                    containString.remove(sChar[left]);
                    left++;
                }
            }
        }
        return max;
    }

那么好，这道题可能很多小伙伴会说太简单了，如果双指针只有这水平，那大家都可以洗洗睡了，还在算法的题海里面挣扎个什么劲。我们接着往下看第二种，收尾指针，刚好也有一道比较经典的题：

11. 盛最多水的容器

如果放在几年前，在我功力还不是那么深厚的时候，我一看这题目，果断给他来个双层循环，暴力计算出所有两个坐标之间的面积，记录一个最大值，然后比较更新，10分钟代码我就给它撸完。然后一跑，尴尬了，暴力的居然还能过，只是这速度和内存的使用情况，有点不太好看。

但是现在嘛，首尾指针给它安排上，两个指针指向的数值，比较小的往对方靠拢（为什么这样自己去想想），记录一个最大值，不断刷新满足条件的值，直到两个指针相遇，结束。

public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0; // 记录中间过程满足条件最大值
        while (left < height.length &amp;&amp; right > left) {// 满足指针继续移动
            int curretn = (height[left] > height[right] ? height[right] : height[left]) * (right - left);
            max = curretn > max ? curretn : max;
            if (height[left] >= height[right]) {// 右指针左移
                right--;
            } else { // 左指针右移
                left++;
            }
        }
        return max;
    }

好，前面两种都介绍完了，下面就轮到固定间距双指针了，但是尴尬的是我居然没找到相关类型的题目，额，先跳过，这种类型的题目一般是滑动窗口会用的比较多，下次遇到了我再更新到这里来，我们先看下两个指针指向不同序列这种类型，这个比较有意思，刚好之前也遇过：

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        int min = intervals[0][0];
        int max = intervals[0][1];
        List<int[]> resultList = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (max >= intervals[i][0]) {
                // 存在交集，合并
                max = max > intervals[i][1] ? max : intervals[i][1];
                continue;
            } else {
                // 不存在交集，将min和max先入结果集，然后再重置min和max
                int[] tempResult = {min, max};
                resultList.add(tempResult);
                min = intervals[i][0];
                max = intervals[i][1];
            }
        }
        resultList.add(new int[] {min, max});

        return resultList.toArray(new int[resultList.size()][2]);
    }
}

两个指针min和max，指向不同的列，找出相交的集合，并返回。

双指针的题目一般情况下都不会很难，从我刷的题目经验来看，顶多中等题吧，关键在于有双指针解题的思想（就是看到问题第一时间能够知道使用双指针解题的思路），下面列一下在leetCode上使用双指针思想解题的题目，供大家练手：
5. 最长回文子串
11. 盛最多水的容器
15. 三数之和
18. 四数之和
26. 删除有序数组中的重复项
27. 移除元素
31. 下一个排列
83. 删除排序链表中的重复元素
160. 相交链表
283. 移动零
392. 判断子序列
821. 字符的最短距离
870. 优势洗牌
905. 按奇偶排序数组
986. 区间列表的交集