核心套路

学习算法和刷题的框架思维

学习解决问题的思路、套路、框架，养成“框架思维”，不应该纠结于问题的细节，把握问题的共性和本质，做到举一反三。

数据结构的存储方式

数据结构的底层存储方式只有两种：数组（顺序存储）和链表（链式存储）。

其他的数据结构，比如哈希表、栈、队列、堆、树、图等都是属于具体的上层建筑，都是在数组或者链表上的特殊操作，只是API特性不同而已。

数组

数组由于是紧凑连续存储，因此可以随机访问，通过索引快速找到对应的元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配足，所以数组如果要扩容，需要先重新分配一块更大的空间，再把数据全部复制进去，时间复杂度为O(N)；而且如果想在数组中间和开始位置进行插入和删除操作，每次必须移动后面的所有数据以保持连续，时间复杂度为O(N)。

数组在开始、中间、最后位置的增删改查分析如下：

开始位置：增加和删除都需要挪动元素，所以效率不高，但是查询和修改就比较高效。
中间位置：增加和删除都需要挪动元素，所以效率不高，但是查询和修改就比较高效。
最后位置：增加和删除位置不需要挪动元素，效率比较高，同时查询和修改效率也比较高。

链表

链表因为元素不连续，靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后继，操作指针即可删除该元素或者插入新元素，时间复杂度为O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，因此会消耗相对更多的存储空间。

链表在开始、中间、最后位置的增删改查分析如下：

开始位置：增加和删除元素只需要操作指针，效率较高，查询和修改元素就在头节点不需要进行遍历，所以效率也比较高。
中间位置：增加和删除元素只需要操作指针，效率较高，查询和修改元素需要从头节点开始进行遍历，时间复杂度为O(N)，所以效率不高。
最后位置：增加和删除元素只需要操作指针，效率较高，查询和修改元素需要从头节点开始进行遍历，时间复杂度为O(N)，所以效率不高。

综上所述：

如果想要查询和修改比较高效，那就使用数组的底层结构。
如果想要插入和删除比较高效，那就使用链表的底层结构。

数据结构的基本操作

任何的数据结构其基本操作就是遍历+访问，在详细一点就是：各种数据结构在不同的应用场景下尽可能高效地进行增删改查。

各种数据结构的遍历+访问无非就是两种形式：线性（for/while迭代）和非线性（递归）。

数组遍历框架，是典型的线形结构：

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        //迭代访问arr[i]
    }
}

链表遍历框架，兼具迭代和递归结构：

class ListNode {
    int val;
    ListNode next;
}

void traverse1(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        //迭代遍历p.val
    }
}

void traverse2(ListNode head) {
    //前序遍历head.val
    traverse2(head.next);
    //后序遍历head.val
}

二叉树具有前序遍历、中序遍历、后序遍历，其实链表也有前序遍历和后序遍历。如果在前序遍历的位置打印head.val，那么就是正序打印链表；如果在后序遍历的位置打印head.val，那么就是倒序打印链表。

二叉树遍历框架，是典型的非线性递归遍历结构：

class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    //前序遍历
    traverse(root.left);
    //中序遍历
    traverse(root.right);
    //后序遍历
}

通过上面的代码可以看到二叉树的遍历与链表的遍历方式非常相似，所以可以将遍历方式扩展到N叉树。

N叉树的遍历框架如下所示：

class TreeNode {
    int val;
    TreeNode[] childrens;
}

void traverse(TreeNode root) {
    for (TreeNode children : root.childrens) {
        traverse(children);
    }
}

N叉树的遍历又可以扩展到图的遍历，因为图就是好几个N叉树的结合体。但是图有可能出现环，这其实很好解决，使用布尔数组visited做标记就可以了。所谓的框架思维就是记住这些遍历框架，根据具体问题在框架上添加代码即可。

算法刷题指南

数据结构和算法

数据结构是工具，算法是通过合适的工具解决特定问题的方法。

先刷二叉树，因为二叉树是最容易培养框架思维的，而且大部分的常考算法本质上都是树的遍历问题。
试着从框架看问题，而不要纠结于细节。

动态规划解题套路框架

回溯算法解题套路框架

全排列问题

N皇后问题

最后总结

BFS算法套路框架

BFS（广度优先搜索-Broad First Search）和DFS（深度优先搜索-Depth First Search）是两种特别常用的算法，其中DFS可被认为就是前面的回溯算法。
BFS核心思想：把一些问题抽象成图，从一个点开始，向四周扩散，一般来说，BFS都是用队列这种数据结构，每次都是将一个节点周围的所有节点加入队列。
BFS和DFS的区别：BFS找到的路径一定是最短的，但代价是空间复杂度要比DFS大很多。

算法框架

BFS出现的场景：问题的本质就是让你在一幅图中找到从起点到终点的最近距离。所谓的BFS本质就是解决该问题的，但是实际中很多题目的描述都是这个本质场景的各种变体，要把现实问题的场景抽象成一幅图，使用BFS的思想进行求解。

框架如下：

int BFS(Node start, Node target) {
    //核心数据结构，节点类型的队列
    Queue<Node> q;
    //记录已经走过的节点，避免走回头路
    Set<Node> visited;

    //将起点加入队列中
    q.offer(start);
    visited.add(start);
    //记录扩散的步数
    int step = 0;

    //队列非空执行
    while (q not empty){
        //获取队列长度
        int sz = q.size();
        //将当前队列中的所有节点向四周扩散
        for (int i = 0; i < sz; i++) {
            //取出队列头元素
            Node cur = q.poll();
            //划重点：这里判断是否达到终点
            if (cur is target){
                return step;
            }
            //将cur的相邻节点加入队列
            for (Node x : cur.adj()) {
                //判断当前节点是否被访问过
                if (x not in visited){
                //加入相邻节点到队列中
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        //划重点：队列中的数据已经更新为新的数据，在这里更新步数
        step++;
    }
    return step;
}

变量解释

q就是核心的队列数据结构；
cur就是当前节点，即队列的头元素；
cur.adj()泛指与cur相邻的所有节点，比如在二维数组中，cur上下左右四面的位置就是相邻节点；
visited的主要作用是防止走回头路，大部分时候都是必需的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要visited；

二叉树的最小高度

需求：计算一棵二叉树的最小高度，输入一棵二叉树，计算它的最小高度，也就是根节点到叶子节点的最短距离。
分析：起点是什么？root！终点是什么？cur.left == null and cur.right == null!

代码如下：

/***
 * @Description: 二叉树节点
 * @Author: Mr.Tong
 */
class TreeNode {
    int val;
    TreeNode left, right;
}

/***
 * @Description: 二叉树的最小高度
 * @Author: Mr.Tong
 */
int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int depth = 1;//root本身就是一层
    while (!q.isEmpty()) {
        int size = q.size();
        //队列中所有节点向四周扩散
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            //判断当前节点是不是终点
            if (cur.left == null && cur.right == null) {
                return depth;
            }
            //将当前节点相邻的所有节点放入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        //更新步数
        depth++;
    }
    return depth;
}

理解

整个算法过程通过画图可以很容易的理解，后面的几个LeetCode题目也建议通过画图的方式加深对BFS思想的理解。

两个问题

为什么BFS可以找到最短距离，DFS不行吗？

BFS的逻辑是depth每增加一次，队列中所有节点都向前迈了一步，这个逻辑保证了一旦找到一个终点，走的步数是最少的，BFS的时间复杂度最坏情况是O(N)。
DFS也是可以找到最短路径的，时间复杂度也是O(N)，但是实际上比BFS低效很多。这是因为DFS是靠递归的堆栈记录走过的路径的，如果要找到最短路径，肯定要把二叉树中的所有树杈都走完，然后才能对比得到最短路径，但是BFS借助队列可以做到一步一步“齐头并进”，是可以在还没遍历完整的一棵树的时候就可以找到最短距离。
总结一下：DFS是线，BFS是面，DFS是单打独斗，BFS是集体行动。

既然BFS那么好，那么为什么还需要DFS？

BFS是可以找到最短路径，但是其空间复杂度高，而DFS的空间复杂度较低。
假设有一棵树是满二叉树，节点数为N，对于DFS算法来说，空间复杂度无非就是递归堆栈，在最坏情况下顶多就是树的高度，也就是O(logN)。但是对于BFS算法来说。队列中每次都会存储二叉树一层的节点，这样在最坏情况下空间复杂度应该是树的最下层节点的数量，也就是N/2，即O(N)。
BFS还是有代价的，一般来说在找最短路径的时候用的是BFS，其他情况用的还是DFS多一些（递归代码好写）。

LeetCode相关题目

二叉树的最小深度open in new window

二叉树的层序遍历open in new window

二叉树的层序遍历2open in new window

二叉树的最大深度open in new window

N叉树的层序遍历open in new window

二叉树的锯齿形层序遍历open in new window

路径之和open in new window

小总结

BFS是广度优先搜索，其抽象是以图的概念进行说明，但是在二叉树等数据结构中却频繁用到该算法，这是因为二叉树、二维数组等就是图的具体化。

图中某个节点向四周扩散具体到二叉树、二维数组等数据结构分别是：二叉树某个节点扩散到其左右子节点、二维数组某个节点扩散到其上下左右四个子节点。但是树结构一般不用visited来防止走回头路，因为根本就没有子节点到父节点的指针存在，所以不用担心会走回头路。

解开密码锁的最少次数

题目链接：打开转盘锁open in new window
不管所有的限制条件，不管 deadends 和 target 的限制，就思考⼀个问题：如果让你设计⼀个算法，穷举所有可能的密码组合，你怎么做？
- 穷举：总共有 4 个位置，每个位置可以向上转，也可以向下转，也就是有 8 种可能，然后，再以这 8 种密码作为基础，对每个密码再转⼀下，穷举出所有可能。
- 仔细想想，这就可以抽象成⼀幅图，每个节点有 8 个相邻的节点，⼜让求最短距离，这就是典型的 BFS。

穷举所有可能的密码组合

// 将 s[j] 向上拨动⼀次
String plusOne(String s, int j) {
    char[] ch = s.toCharArray();
    if (ch[j] == '9')
        ch[j] = '0';
    else
        ch[j] += 1;
    return new String(ch);
}

// 将 s[j] 向下拨动⼀次
String minusOne(String s, int j) {
    char[] ch = s.toCharArray();
    if (ch[j] == '0')
        ch[j] = '9';
    else
        ch[j] -= 1;
    return new String(ch);
}


// BFS 框架，打印出所有可能的密码
void BFS(String target) {
    // 核心数据结构-队列
    Queue<String> q = new LinkedList<>();
    // 添加根节点
    q.offer("0000");
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向周围扩散 */
        for (int i = 0; i < sz; i++) {
            String cur = q.poll();
            /* 判断是否到达终点 */
            System.out.println(cur);
            /* 将⼀个节点的相邻节点加⼊队列 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                String down = minusOne(cur, j);
                q.offer(up);
                q.offer(down);
            }
        }
        // 队列中的数据已经更新完
        /* 在这⾥增加步数 */
    }
    return;
}
// 1000 9000 0100 0900 0010 0090 0001 0009 -> 第一次更新数据
// ... -> 以上面的八个数为基础进行第二次数据的更新，以此类推

上面的代码可以穷举所有的密码组合，但是还存在如下问题：

会走回头路。比如从0000转到1000之后，在转1000的时候还会转到0000，这样就产生了死循环。
没有终止条件。按照题目要求找到target就应该返回步数。
没有对deadends进行处理。这些死亡密码是不能出现的，所以在碰到这些密码的时候应该跳过。

通过对上述代码进行修改：

class Solution {
    // 将 s[j] 向上拨动⼀次
    String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9')
            ch[j] = '0';
        else
            ch[j] += 1;
        return new String(ch);
    }

    // 将 s[j] 向下拨动⼀次
    String minusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0')
            ch[j] = '9';
        else
            ch[j] -= 1;
        return new String(ch);
    }
    public int openLock(String[] deadends, String target) {
        // 记录需要跳过的死亡密码
        Set<String> deads = new HashSet<>();
        for (String s : deadends) deads.add(s);
        // 记录已经穷举过的密码，防⽌⾛回头路
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        // 从起点开始启动⼴度优先搜索
        int step = 0;
        q.offer("0000");
        visited.add("0000");
        while (!q.isEmpty()) {
            int sz = q.size();
            /* 将当前队列中的所有节点向周围扩散 */
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                /* 判断是否到达终点 */
                if (deads.contains(cur))
                    // 出现死亡密码，直接跳过，开始下一个密码
                    continue;
                if (cur.equals(target))
                  // 返回步数
                    return step;
                /* 将⼀个节点的未遍历相邻节点加⼊队列 */
                for (int j = 0; j < 4; j++) {
                    // 向上转动
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        q.offer(up);
                        visited.add(up);
                    }
                    // 向下转动
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            /* 在这⾥增加步数 */
            step++;
        }
        // 如果穷举完都没找到⽬标密码，那就是找不到了
        return -1;
    }
}

优化

deads集合和visited集合都是记录不合法访问的集合，可以不需要 visited 这个哈希集合，直接将遍历过的元素加到deads集合中，效果是⼀样的，可能更加优雅⼀些。

BFS算法还有一种稍微高级的优化思路：双向BFS，使用双向BFS可以进一步提高算法的效率。

传统的BFS和双向BFS的区别

传统的BFS框架就是从起点开始向四周扩散，遇到终点时停⽌；⽽双向BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停⽌。

从 Big O 表⽰法分析算法复杂度的话，它俩的最坏复杂度都是 O(N) ，但是实际上双向BFS 确实会快⼀些。

按照传统BFS算法的策略，会把整棵树的节点都搜索⼀遍，最后找到target ；⽽双向BFS其实只遍历了半棵树就出现了交集，也就是找到了最短距离，明显实现了效率上的提升。

双向BFS的局限性

双向BFS也有局限，因为必须要知道终点在哪⾥。
⽐如刚才讨论的⼆叉树最⼩⾼度的问题，⼀开始根本就不知道终点在哪⾥，也就⽆法使⽤双向BFS；但是第⼆个密码锁的问题，是可以使⽤双向BFS算法来提⾼效率。

使用双向BFS进行优化：

public int openLock(String[] deadends, String target) {
    // 记录需要跳过的死亡密码
    Set<String> deads = new HashSet<>();
    for (String s : deadends) deads.add(s);
    // ⽤集合不⽤队列，可以快速判断元素是否存在
    Set<String> q1 = new HashSet<>();
    Set<String> q2 = new HashSet<>();
    Set<String> visited = new HashSet<>();
    int step = 0;
    q1.add("0000");
    q2.add(target);
    while (!q1.isEmpty() && !q2.isEmpty()) {
        // 哈希集合在遍历的过程中不能修改，⽤ temp 存储扩散结果
        Set<String> temp = new HashSet<>();
        /* 将 q1 中的所有节点向周围扩散 */
        for (String cur : q1) {
            // 不能出现死亡密码
            if (deads.contains(cur))
                continue;
            /* 判断是否到达终点 */
            if (q2.contains(cur))
                return step;
            visited.add(cur);
            /* 将⼀个节点的未遍历相邻节点加⼊集合 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up))
                    temp.add(up);
                String down = minusOne(cur, j);
                if (!visited.contains(down))
                    temp.add(down);
            }
        }
        /* 在这⾥增加步数 */
        step++;
        // temp 相当于 q1
        // 这⾥交换 q1 q2，下⼀轮 while 就是扩散 q2
        q1 = q2;
        q2 = temp;
    }
    return -1;
}

不再使⽤队列，⽽是使⽤ HashSet ⽅便快速判断两个集合是否有交集。
另外的⼀个技巧点就是 while 循环的最后交换 q1 和 q2 的内容，所以只要默认扩散 q1 就相当于轮流扩散 q1 和 q2 。

双向BFS还有⼀个优化，就是每次将少的那个集合进行扩散，避免轮流扩散q1和q2。

public int openLock(String[] deadends, String target) {
    // 记录需要跳过的死亡密码
    Set<String> deads = new HashSet<>();
    for (String s : deadends) deads.add(s);
    // ⽤集合不⽤队列，可以快速判断元素是否存在
    Set<String> q1 = new HashSet<>();
    Set<String> q2 = new HashSet<>();
    Set<String> visited = new HashSet<>();
    int step = 0;
    q1.add("0000");
    q2.add(target);
    while (!q1.isEmpty() && !q2.isEmpty()) {
        // 哈希集合在遍历的过程中不能修改，⽤ temp 存储扩散结果
        Set<String> temp = new HashSet<>();
        /* 将 q1 中的所有节点向周围扩散 */
        for (String cur : q1) {
            // 不能出现死亡密码
            if (deads.contains(cur))
                continue;
            /* 判断是否到达终点 */
            if (q2.contains(cur))
                return step;
            visited.add(cur);
            /* 将⼀个节点的未遍历相邻节点加⼊集合 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up))
                    temp.add(up);
                String down = minusOne(cur, j);
                if (!visited.contains(down))
                    temp.add(down);
            }
        }
        /* 在这⾥增加步数 */
        step++;
        // 下一轮进行扩散的时候，扩散较少的那个集合
        // 对于temp和q2来说，将最小的那个给q1
        if (temp.size() <= q2.size()) {
            q1 = temp;
        } else {
            q1 = q2;
            q2 = temp;
        }
    }
    return -1;
}

因为按照 BFS 的逻辑，队列（集合）中的元素越多，扩散之后新的队列（集合）中的元素就越多；在双向BFS算法中，如果我们每次都选择⼀个较⼩的集合进⾏扩散，那么占⽤的空间增⻓速度就会慢⼀些，效率就会⾼⼀些。

时间复杂度

⽆论传统BFS还是双向BFS，⽆论做不做优化，从Big O衡量标准来看，时间复杂度都是⼀样的。因为双向BFS的代码只是更换了返回结果的方式（哈希集合是否有交集），每次进行扩散的方式不是并行扩散的，而是轮流进行扩散。

LeetCode相关题目

开密码锁open in new window

双指针技巧套路框架

双指针技巧可以分为如下的两类：

一类是“快慢指针”，主要解决链表中的问题，比如典型的判定链表中是否包含环。
一类事“左右指针”，主要解决数组（或者字符串）中的问题，比如二分搜索。

快慢指针的常用算法

快慢指针一般会初始化指向链表的头节点head，前进时快指针fast在前，慢指针slow在后。

判定链表中是否含有环

链表的特点是每个节点只知道下一个节点，所以一个指针是无法判断链表中是否含有环的。

如果链表中不含环，那么这个指针最终会遇到空指针null，表示链表到头了，可以判断当前链表是不含有环的。

boolean hasCycle(ListNode head) {
    while (head != null) {
        head = head.next;
    }
    return false;
}

如果链表中含有环，上述代码就会陷入死循环，因为环形链表中没有空指针null，无法判断当前链表含有环。

判断单链表中是否有环，经典的算法就是使用双指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到null，说明链表不含环；如果含有环，快指针最终会和慢指针相遇，说明链表含有环。

boolean hasCycle(ListNode head) {
    //定义快慢指针
    ListNode fast, slow;
    //初始化快慢指针都指向头节点
    fast = slow = head;
    while (fast != null && fast.next != null) {
        //快指针每次走两步
        fast = fast.next.next;
        //慢指针每次走一步
        slow = slow.next;
        //如果存在环，快慢指针必然会相遇
        if (fast == slow) {
            return true;
        }
    }
    //循环可以停止，说明单链表中不存在环
    return false;
}

已知链表中含有环，返回这个环的起始位置

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    //快慢指针初始化
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }
    //上面的代码类似于hasCycle函数
    //现在fast=slow，两者相遇，说明链表存在环，并且相遇点肯定是在环内部（包括环起点）的内部的某个节点
    //相遇点不可能在环外部，因为fast虽然跑得快，但是跑不出环
    //先把一个指针重新指向head
    slow = head;
    //现在slow在fast后面，两者在以相同的速度跑，下一次相遇点就是环的起点
    while (slow != fast) {
        //两个指针以相同的速度向前跑
        fast = fast.next;
        slow = slow.next;
    }
    //slow=fast的时候，跳出循环，两个指针再次相遇
    //两个指针再次相遇的那个单链表节点就是环的起点
    return slow;
}

结论：当快慢指针相遇时，让其中任何一个指针指向头节点，然后让两个指针以相同的速度前进，再次相遇时所在的节点位置就是环的起点位置。

寻找无环单链表的中点

最直接的思路：先遍历一遍链表，算出链表的长度n，然后再一次遍历链表，走n/2步，这样就得到了链表的中点。

漂亮的思路：使用双指针，让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头的时候，慢指针就处于链表的中间位置。

ListNode getMidNodeFromList(ListNode head) {
    ListNode fast, slow;
    //初始化快慢指针
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

注意

当链表长度为奇数的时候，slow恰巧停留在中间位置；当链表长度为偶数的时候，slow最终的位置是中间偏右。

寻找链表中点作用

寻找链表中点的一个重要作用是对链表进行归并排序，可以尝试参考数组的归并排序写出链表的归并排序。

寻找单链表的倒数第K个元素

使用快慢指针，让快指针先走k步，然后快慢指针开始以相同速率前进，这样当快指针到链表末尾的时候，慢指针所在的位置就是链表倒数第k个节点（为了简化，假设k不会超过链表长度）。

ListNode findKNodeFromListEnd(ListNode head, int k) {
    ListNode fast, slow;
    fast = slow = head;
    //快指针先走k步
    while (k != 0) {
        fast = fast.next;
        k--;
    }
    //快慢指针以相同的速率跑
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    //此时slow所在的节点就是倒数第k个节点
    return slow;
}

LeetCode相关题目：

剑指Offer22.链表中倒数第k个节点open in new window

面试题02.02.返回倒数第k个节点open in new window

剑指OfferII022.链表中环的入口节点open in new window

左右指针的常用算法

左右指针一般运用在数组问题中，实际就是两个索引值，一般初始化规则如下：

left=0;

right=length(array)-1;

二分搜索

后续会有二分搜索的细节描述，在此给出最简单的二分查找算法，旨在突出其双指针特性。

/***
 * @Description: 二分查找算法，默认nums数组升序
 * @Author: Mr.Tong
 */
int binarySearch(int[] nums, int target) {
    //初始化左右指针
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;//找到就返回其索引
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    //找不到直接返回-1
    return -1;
}

两数之和

输入一个已按照升序排列的有序数组nums和一个目标值target，在nums中找到两个数使得它们相加之和等于target，请返回这两个数的索引（可以假设这两个数一定存在，索引从1开始）。

只要数组有序，就应该想到使用双指针技巧，通过sum的大小来调节left和right的移动。

/***
 * @Description: 两数之和
 * @Author: Mr.Tong
 */
int[] twoSum(int[] nums, int target) {
    //左右指针初始化
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum > target) {
            //让sum小一点
            right--;
        } else if (sum < target) {
            //让sum大一点
            left++;
        }
    }
    //找不到
    return new int[]{-1, -1};
}

反转数组

虽然很多编程语言提供了原地反转数组的API，但是仍然要懂得其原理。

/***
 * @Description: 原地反转数据
 * @Author: Mr.Tong
 */
void reverse(int[] nums) {
    //初始化左右指针
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        //交换左右两个指针指向的数据
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        //指针移动
        left++;
        right--;
    }
}

滑动窗口算法

滑动窗口算法是双指针技巧的最高境界，严格讲，它是快慢指针在数组（字符串）上的应用。若掌握该算法，可以解决一大类字符串匹配问题。该部分比前面稍微复杂，可以查看后续的滑动窗口算法框架。

二分搜索算法

一个笑话

有一天阿东到图书馆借了N本书，出图书馆的时候，警报响了，于是保安把阿东拦下，
要检查哪本书没有登记出借。阿东正准备把每一本书放在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分搜索都不会吗？

于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成
两堆。最终，检测了logN次之后，保安成功地找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是阿东背着剩下的书走了。

从此，图书馆丢了N-1本书。

二分搜索并不简单，Knuth“大佬”（发明KMP算法的那位）是这么评价二分搜索的：

Although the basic idea of binary search is comparatively straightforward, the details canbe surprisingly tricky.

说人话就是：思路很简单，细节是魔鬼。

其细节在于到底要给mid加1还是减1，while里面到底是<=还是<。

二分搜索框架

基础框架如下所示，后面的二分搜索的变形都是基于该框架。

/***
 * @Description: 二分搜索框架
 * @Author: Mr.Tong
 */
int binarySearch(int[] nums, int target) {
    int left = 0;
    int right =...;
    while (...){
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left =...;
        } else if (nums[mid] > target) {
            right =...;
        }
    }
    return ...;
}

注意：

不要出现else，而是使用else-if考虑到所有的情况，可以清楚展现细节。
...标记的地方都是出现细节问题的地方。
int mid = left + (right - left) / 2是为了防止溢出。

寻找一个数（基本的二分搜索）

需求：在一个有序数组中查找一个数，如果找到就返回其索引，如果找不到就返回-1。

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;//注意
    while (left <= right) {//注意
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;//注意
        } else if (nums[mid] > target) {
            right = mid - 1;//注意
        }
    }
    //循环跳出，找不到就返回-1
    return -1;
}

问题一：为什么while循环的条件中是<=，而不是<？
问题二：为什么left = mid + 1和right = mid - 1？有的代码是right = mid或者left = mid，没有这些加加减减，到底是怎么回事？怎么判断？
问题三：该算法有什么缺陷？