Talk is cheap. Show me the code.

尽管面试考察算法时常存在争议，但不可否认的是，算法和数据结构是程序员的基本功。更一般的，Coding以及对每一行代码的理解是最能直接反映程序员的真实水准的。因此，算法面试就像XX，如果反抗不了，就尽情享受吧。

本文以Java为编程语言，结合笔者纵横各种面试场的经验，归纳总结了高频算法题（Coding题）及其解题思路和语言要点，帮助你使用最短时间快速刷题，通过面试，拿到心仪的offer。

链表

链表相关题目考察频率极高，同时链表题目相对独立，一般不需要借助其他数据结构，解题思路也比较固定。

1. 链表必会技能——反转链表（打死也得会写）

技巧：③→②→①→④，写这么一个中间态，要想实现③②①作为整体和④的反转，需要维护以下指针：

需要一个tail尾指针，tail指针永远指向最初的头节点，一直迭代到它的next为空，成为真正的尾节点；

需要一个临时的newHead头指针，在交换过程中不断地指向新的头节点，也就是tail的next节点；

复用原始head指针，每次交换完成后，临时temp赋值给真正head。

具体节点交换过程其实非常容易写，记住这句话想不会都难：上一行读值的节点，下一行对其写值，往复四次。

public ListNode reverseList(ListNode head) {
    if (head != null) {
        ListNode tail = head;
        ListNode newHead;
        while (tail.next != null) {
            //四行代码规律明显，上一行读值的节点，下一行对其写值
            newHead = tail.next;
            tail.next = newHead.next;
            newHead.next = head;
            head = newHead;
        }
    }
    return head;
}

很多题目都是以反转链表为基础的：

（必会题）反转 链表 ： leetcode.cn/problems/re…

（必会题）反转 链表 Ⅱ： leetcode.cn/problems/re…

有两种解法（可以看官方题解）：

第一种理解起来更加清晰但代码可能相对冗长：

1. 就是通过遍历找到反转区间的前一个节点和后一个节点；
2. 把反转区间的尾节点的next置为空，从而完全按照标准的反转链表的方式来反转这段区间；
3. 最后再把反转后的区间链表与前置节点和后置节点进行重连。

第二种基于标准反转链表做些改动，代码会比较简洁：

1. 首先稍微改变下反转链表的循环终止条件，从next为null改为限定迭代的步数；
2. 然后用前置节点prev.next来代替反转过程中的head指针，这样可以省略反转后的区间链表与前置节点的重连；
3. 同时因为没有把区间链表的next置为null，而区间链表的反转并不会改变区间链表与后置节点的连接状态，因此后置节点也不需要重连。

（进阶题）K个一组翻转 链表 ： leetcode.cn/problems/re…

1. 链表技巧之——dummyHead

上面题目反转 链表 Ⅱ需要格外注意的一个边界情况是因为反转区间有可能是从头节点开始，这就需要我们在写代码时额外增加两段逻辑的处理：一是前置节点为空的情况，二是最后不能直接返回原始头节点。其实链表问题经常存在这种迭代过程中需要单独处理头节点的情况，此时有一个小技巧是：开局先来一个哑节点指向头节点，这样一来，迭代过程中就不需要对头节点进行特殊判断了，最后只需要返回哑节点的next即代表处理后链表的头。

ListNode dummyHead = new ListNode();
dummyHead.next = head;
...
return dummyHead.next;

如下两道题也可应用该技巧：

（必会题）合并两个有序 链表 ： leetcode.cn/problems/me…

（高频题）两两交换 链表 中的节点： leetcode.cn/problems/sw…

1. 链表技巧之——快慢指针

快慢指针或者叫双指针也是经典的解决链表问题的技巧，实际场景中有两种：一种走的快，一种走的早。

倒数节点问题用走的早的：

（必会题）删除 链表 的倒数第n个结点： leetcode.cn/problems/re…

消除链表长度差用走的早的：

（必会题）相交 链表 ： leetcode.cn/problems/in…

寻找链表交点问题的思路：是在较长链表中找到一个节点作为长链表的起点，短链表的起点就是头节点，然后让两个指针同步向前，直到步入同一节点即为交点。因此需要消除两个链表的长度差，而消除长度差最朴素的方式就是两个快指针分别遍历两个链表求得各自长度。稍加优化就是，当短链表快指针走到末尾的时候，长链表慢指针从长链表头开始出发，当长链表快指针走到末尾的时候，长链表慢指针刚好抵达我们上述的目标起点，这时再让短链表慢指针从短链表头开始出发，两个慢指针第一次相遇的点就是相交节点（具体代码写起来会有一种特别精简的方式，可以参考官方题解）。

环问题用走的快的：

（必会题）环形 链表 ： leetcode.cn/problems/li…

（高频题）环形 链表 Ⅱ： leetcode.cn/problems/li…

找入环点要推导下快慢指针的路程等式，从而计算出各段的距离关系。

树

主要就是二叉树，面试中考察频率最高的除了链表就是二叉树。几乎所有二叉树的算法题都可以用递归的方式解决，因此先介绍下递归。

递归

背下这个递归范式：

public int recursion(level，param1，param2，...) {
    //1.base case（递归终止条件）
    if(level > MAX_LEVEL){
        return -1;
    }
    //2.当前层的处理逻辑
    processCurrent(param1,param2,...)
    //3.向下一层递归
    int result = recursion(level+1,...)
    //4.（可选）使用下一层递归的结果
    processResult(result)
}

（高频题）Pow(x,n)： leetcode.cn/problems/po…

递归有个小技巧要记住，是可以往参数里传一个集合类型，然后在不断的递归过程中往这个集合填充数据，这种方式也被称为回溯，可以解很多题目，比如：

（高频题）括号生成： leetcode.cn/problems/ge…

括号生成的两步法：

1. 先想着可以用构造一棵树的思路来罗列所有可能的情况；
2. 然后想到其实不用传入树的节点，递归函数可以传入一个string和string的集合，递归到最后把string添加到string集合。

回到二叉树，解二叉树问题除了使用递归，还有就是引入队列或者栈，进行节点的迭代了。如果对于队列或者栈还不太熟悉的话可以先跳到后面看下关于队列和栈的介绍，然后再回来刷二叉树的题。

二叉树题目核心就是节点的遍历，因此不得不提两种搜索方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索 ： 使用栈，沿着左子树路径一路往下，同时入栈沿途节点，到底后往回返，节点出栈；如果返回过程中出栈的上级节点有右子节点，对右子节点重复使用深度优先搜索。

写深度优先搜索的时候一般直接使用递归，相当于复用了递归本身的栈结构。

深度优先搜索对应到二叉树，其实就是最常见的前序遍历（根左右）、中序遍历（左根右）与后序遍历（左右根）。相应的，这几种遍历直接使用递归代码异常简单，当然也可以使用迭代，代码会相对复杂一些，如前面所说需要手动引入一个栈。

这里提一下图，其实单链表相当于树的特殊情况，树相当于图的特殊情况，那图的DFS、BFS同树的思路一致，唯一区别是遍历过程中需要一个额外的set来存放已经visited的节点。

（必会题）二叉树的 前序遍历 ： leetcode.cn/problems/bi…

（必会题）二叉树的 中序遍历 ： leetcode.cn/problems/bi…

（必会题）二叉树的 后序遍历 ： leetcode.cn/problems/bi…

广度优先搜索： 使用队列，出队本层元素，入队下层元素；也可以使用递归，递归函数传入一个level层数即可。

（必会题）二叉树的层序遍历： leetcode.cn/problems/bi…

其他二叉树高频题目：

（高频题）二叉树的最近公共祖先： leetcode.cn/problems/lo…

思路是用递归去左右子树寻找p和q：

1. 递归函数退出条件是当前节点等于p或q或null；
2. 否则同时递归左、右子树继续寻找p或q；
3. 拿到递归结果后的处理是如果左右子树都找到了，那最近公共祖先就是根；如果左找到了，右没找到，那最近公共祖先就是左；反之为右；
4. 因为递归过程的返回是自下而上，所以结果一定是最近的。

（高频题）二叉树的最大深度： leetcode.cn/problems/ma…

（高频题）二叉树的最小深度： leetcode.cn/problems/ma…

求二叉树最小深度有个特殊case是如果根节点没有左子树或右子树，则最小深度不是1，要注意。

（高频题）验证 二叉搜索树 ： leetcode.cn/problems/va…

二叉搜索树中节点均满足：左子树比根小，右子树比根大，所以中序遍历是有序的。

验证二叉搜索树，写递归函数，传入当前节点需要满足的最大值和最小值区间，起始取Long.MAX_VALUE和Long.MIN_VALUE：

1. 退出条件是当前的node为空，返回true；
2. 否则判断node是否比min大，比max小，且递归判断左节点和右节点是否也满足条件，同时更新最大值（左）或最小值（右）为当前node的值。

（高频题）对称二叉树： leetcode.cn/problems/sy…

（高频题）翻转二叉树： leetcode.cn/problems/in…

（高频题）二叉树展开为 链表 ： leetcode.cn/problems/fl…

队列

无论是解算法题还是实际开发中，队列都是最常用的数据结构之一，Java中的队列就是实现Queue接口的类。

Queue接口常用方法有两组：

1. add、remove、element（遇到边界时抛出异常）
2. offer、poll、peek（遇到边界时返回特殊值）

常用实现类：实现了Deque接口（双端队列，继承自Queue）的子类：

1. ArrayDeque（基于数组）
2. LinkedList（基于双向链表）

Deque接口新增方法有两组：

1. addFirst、addLast、removeFirst、removeLast、getFirst、getLast（遇到边界时抛出异常）
2. offerFirst、offerLast、pollFirst、pollLast、peekFirst、peekLast（遇到边界时返回特殊值）

当Deque用作普通队列时，始终尾进头出，可以直接使用上述Queue接口中定义的方法。关于Deque接口更加详细的介绍可以查阅Doc。

（进阶题）滑动窗口最大值： leetcode.cn/problems/sl…

此外，如果需要线程安全的队列可以使用无锁线程安全的ConcurrentLinkedQueue和ConcurrentLinkedDeque。

阻塞队列

阻塞队列是为多线程场景而生的，Java中的阻塞队列是实现了BlockingQueue接口的子类：

1. ArrayBlockingQueue
2. LinkedBlockingQueue

BlockingQueue相比Queue增加了一些支持线程阻塞的方法，比如：

1. take（队列为空阻塞）和put（队列满时阻塞）组合
2. 带有超时时间参数的poll和offer组合，可以让线程最多阻塞指定时间后方法返回

BlockingQueue常应用在多线程编程下，多线程问题也是Coding面试的高频题目：

（必会题）实现生产者-消费者模式

生产者-消费者模式一般有三种实现方式：

• 最常规的是使用wait/notify实现生产者-消费者：

//生产者
while (true) {
    synchronized (queue) {
        try {
            while (queue.size() == capacity) {
                queue.wait();
            }
            queue.offer(new Object());
            queue.notifyAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}
//消费者
while (true) {
    synchronized (queue) {
        try {
            while (queue.isEmpty()) {
                queue.wait();
            }
            queue.poll();
            queue.notifyAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

如果使用wait/notify，有两个要点要注意：

1. wait方法外面要用while循环包裹，而不能用if条件包裹。

   主要原因是多个生产者或消费者的场景下，消费者A有可能消费完后唤醒了消费者B，所以消费者B被唤醒后需要再次去判断队列是否为空，因此需要用while循环，生产者同理。

2. 要使用notifyAll而非notify去唤醒其他线程。

   notify方法和notifyAll方法的根本区别是：前者只能使得一个处于WAITING状态的线程转化为BLOCKING状态，而后者可以使得所有处于WAITING状态的线程转化为BLOCKING状态。 而转化为BLOCKING的意义是：当持有锁的线程最终执行完同步代码块后，处于BLOCKING状态的线程才有机会去获得锁。 所以同样是多个生产者或消费者的场景下，会有这么一种情况，当所有的生产者处于WAITING状态，但消费者消费完数据后，调用notify方法唤醒的是另一个消费者，因为此时数据队列为空，所以马上这个消费者会调用wait方法进入WAITING状态，重复此种情况，最终所有的消费者也都进入到了WAITING状态，解决就是所有线程都陷入了WAITING状态。

• 使用await/signalAll实现生产者-消费者

• 使用BlockingQueue实现生产者-消费者

使用BlockingQueue可以写出非常简洁的生产者-消费者代码。其实BlockingQueue内部就是依赖ReentrantLock和await/signalAll来实现线程的同步和阻塞的。

关于这三种方式的实现可以参考《从根上理解生产者-消费者模式》。

（必会题）实现线程池

实现线程池的核心就是使用BlockingQueue，只要围绕几个核心参数（corePoolSize、maximumPoolSize、keepAliveTime、workQueue、handler），理解它们的机制，就不难实现一个简化版本的线程池。

理解线程池原理可以参考《24张图带你彻底弄懂Java线程池》。

优先级队列

Java中的优先级队列是PriorityQueue类，它的内部实现基于二叉堆（binary heap）。

二叉堆可以看作是一个完全二叉树：除了最底层，其他每层都是完全填满的，且所有节点都是从左向右添加，同一层级的元素在二叉堆中没有大小关系。

元素插入时，先放置在堆的末尾，然后循环与其parent对比，上浮shiftup到合适的位置；

元素移除时，通常是移除栈顶元素，然后用最后一个元素移动到栈顶，然后循环将其与两个child对比，下沉shiftdown到合适位置。

Java的PriorityQueue默认是一个小顶堆（根节点元素最小），最小堆的主要特性就是每次poll的是最小元素，相当于可以靠出队来获得增序序列。

如果想要获得降序序列，那就要使用大顶堆，可以通过构造优先级队列的时候传入一个自定义的比较器来实现：

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(CAPACITY, new Comparator<Integer>(){
        @Override
        public int compare(Integer o1, Integer o2) {
            //升序返回：o1-o2，降序返回：o2-o1 
            //想要记住这个规则，可以先记住升序需要return -1，降序需要return 1，然后假设o1<o2
            return o2-o1;
        }
   });

（高频题）数据流中第K大元素： leetcode.cn/problems/kt…

栈

栈和队列均为数据结构的基础，Java类库中的栈主要有两类：

• Stack：继承自Vector，因此是线程安全的，线程安全主要靠核心方法都被synchronized修饰来实现。主要方法：push、pop、peek、empty。
• 同队列一样，因为Deque接口是双端队列，头尾可以任意进出，所以完全可以把Deque接口的子类ArrayDeque和LinkedList来当作栈使用。当Deque用作栈的时候，始终头进头出，可以直接使用push、pop、peek方法，等效于遇到边界抛异常的只在头部操作的方法：addFirst、removeFirst、getFirst。

（必会题）最小栈： leetcode.cn/problems/mi…

最小栈用两个栈来实现，唯一要注意的是入栈的时候要<=，不能<。

（高频题）有效的括号： leetcode.cn/problems/va…

哈希表

哈希表是用空间换时间的化身，是大量算法题想要优化时间复杂度的最有利的工具。

Java里面哈希表的代表就是Map接口和Set接口的子类。

顺带说下Java集合类框架主要就是Collection接口和Map接口，Collection接口下面有List、Set、Queue接口。

哈希表最常用的实现类就是HashMap和HashSet，其中HashSet其实就是通过内部持有一个HashMap，value始终存一个空字符串来实现，所以可以理解为是一种特殊的HashMap。

HashMap使用频率非常高，同时也是面试高频考点，因此需要阅读源码、分析细节、熟练掌握其内部机制如：

1. 数组、链表、红黑树的搭配；
2. 插入元素时计算hash、计算index、更新或新增节点的完整过程；
3. 扩容策略和扩容时元素的移动。

同时有能力自己去实现一个简化版本的HashMap。

另外，常用的方法一定要熟记，比如非常实用的getOrDefault，详见Doc。

（必会题）字母异位词分组： leetcode.cn/problems/gr…

（必会题） LRU 缓存： leetcode.cn/problems/lr…

直接使用Java的LinkedHashMap（HashMap+双向链表）可以很容易构造一个LRUCache：

class LRUCache {

    private Map<Integer, Integer> map;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry entry) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }

}

但实际算法面试中，一般都禁止直接使用LinkedHashMap，所以需要使用HashMap和自定义双向链表去实现。

（高频题）实现Trie（前缀树）： leetcode.cn/problems/im…

HashMap往往在解数组相关问题时使用频率很高，因此更多题目在数组部分介绍。

数组

数组作为提供输入的最常规的方式，相关题目种类多样。首先要熟练掌握Java中数组的定义、初始化以及和集合类框架的转换等操作。

// 创建一个整数数组，长度为5
int[] numbers = new int[5];
// 创建并初始化一个字符串数组
String[] fruits = {"Apple", "Banana", "Cherry"};
// 将数组转换为List，Arrays.asList(数组)返回的是一个只读的List，不能add、remove
// 数组转换为List也可使用Collections.addAll(List，数组)方法
List<String> list = Arrays.asList(fruits);
// 将List转换为数组，如果使用的是无参的toArray方法，返回的类型是Object[]，不能强转         
String[] array = list.toArray(new String[0]);
// 创建一个二维数组
int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
// 访问二维数组的元素
int value = matrix[1][2]; // 获取第二行第三列的值

一维数组

1. 避免两层循环遍历数组，考虑使用哈希表，空间换时间，O(n)时间解决。

（必会题）两数之和： leetcode.cn/problems/tw…

1. 遇到数组当中连续子数组相关问题的，想到用前缀和O(n)时间解决。

（高频题）和为K的子数组： leetcode.cn/problems/su…

（高频题）除自身以外数组的乘积： leetcode.cn/problems/pr…

1. 轮转数组小技巧：三次翻转。

（高频题）轮转数组： leetcode.cn/problems/ro…

二维数组

二维数组常用优化经验之一是复用原数组空间，原地计算，不引入额外空间，从而把空间复杂度降到O(1)。

（高频题）矩阵置零： leetcode.cn/problems/se…

用第一行、第一列来存储每一行、每一列的特征，同时再用两个常数来存储第一行、第一列的特征。

（高频题）旋转图像： leetcode.cn/problems/ro…

(m,n)→(n,len-1-m)

（高频题）岛屿数量： leetcode.cn/problems/nu…

属于网格问题可以套模板：遍历+标记+递归访问周围节点，推荐看这篇题解：岛屿类问题的通用解法、DFS 遍历框架

滑动窗口

滑动窗口问题的通用思路：两层循环

1. 每次先滑right指针，滑倒满足要求；
2. 然后再滑left指针，滑倒满足要求的前提下最优，记录到结果，重复1、2步；
3. 滑动过程中结合HashSet或HashMap来做记录。

推荐看这篇题解：我写了一首诗，把滑动窗口算法变成了默写题

（高频题）无重复字符的最长子串： leetcode.cn/problems/lo…

（高频题）找到字符串中所有字母异位词： leetcode.cn/problems/fi…

动态规划

不要被动态规划这几个字吓退，核心其实就是递推。具体分为三个步骤：

1. 递归+记忆化→递推

   很多动态规划问题是可以递归求解的，但如果当前值f(n)=g(f(n-1),f(n-2))，比如典型的斐波那契数列问题，那简单的递归写法会造成大量的重复计算，所以这时可以引入一个数组或哈希表来作为“备忘录”，存取已经计算过的中间值，这就是记忆化，可以大大降低时间复杂度。更进一步，递归的写法往往是自顶向下或者说从大到小，但实际真正的计算是以base case为起点，相应地，备忘录里存储的值也是从小到大，因此完全可以把递归转化为迭代的方式，这就叫递推。

2. 状态的定义与状态转移方程：

   当我们有了递推这个武器之后，那动态规划问题的核心就是状态的定义以及状态转移方程了。所谓状态，其实就是要求解的目标，往往就是以n为变量的一个函数f(n)，而所谓状态转移方程便是这个f(n)和其他状态的数学关系，比如对于斐波那契数列f(n)=f(n-1)+f(n-2),n>2，这是这是一维的例子，实际题目中还存在二维的状态定义。显然，如果我们能定义出来状态转移方程，那代码就很好写了，所以动态规划问题的难点往往就在于归纳总结出状态转移方程。

3. 最优子结构

   像斐波那契数列这样的问题严格来讲，只是属于递推的问题，它的递推过程不涉及求最优值。而真正的动态规划问题往往是多条道路里寻找最优的一条，因此需要在递推过程的每一步计算局部最优解（从这个角度来讲动态规划=递推+贪心），从而形成最终的最优子结构，反映到状态转移方程就是需要引入min或max函数。

关于动态规划的更完整的解题思路可以参考这篇题解：动态规划套路详解。

（必会题）斐波那契数： leetcode.cn/problems/fi…

（必会题）爬楼梯： leetcode.cn/problems/cl…

（高频题）三角形最小路径和： leetcode.cn/problems/tr…

（高频题）买卖股票的最佳时机： leetcode.cn/problems/be…

单例

（必会题）实现单例

对单例的考察也经常出现在Coding面试中，双重检查锁和静态内部类方式的单例都是需要熟记于心的，另外一定要注意合理的权限修饰符的使用，包括别忘了将构造方法私有化。

双重检查锁：

public class Singleton {  
    private volatile static Singleton singleton;  
    private Singleton (){}  
    public static Singleton getSingleton() {  
        if (singleton == null) {  
            synchronized (Singleton.class) {  
                if (singleton == null) {  
                    singleton = new Singleton();  
                }  
            }  
        }  
        return singleton;  
    }  
}

老生常谈的两个问题：

1. 两次if判断的作用：减少同步的开销，同时确保单例对象的线程安全性。具体而言，第一次if判断有助于在已经完成实例化的情况下，线程不必获取锁才能获取实例，减少同步开销；第二次if判断主要是线程B在第一次if判断执行完然后获取到锁之前的这段时间，线程A可能已经执行完同步代码块并完成了实例化，因此线程B获取到锁之后要二次判断。
2. volatile关键字在此处的作用：保证可见性以及防止指令重排序。具体而言，Java内存模型允许线程将共享变量的值缓存在CPU中，所以如果不用volatile关键字修饰，那有可能线程A虽然已经完成了实例化，但还并没有将实例同步到内存中，因此线程B看到的变量依然为null；另一方面，实例化对象的语句可能对应三个指令：①分配内存空间、②初始化对象、③将内存地址赋值给变量，但如果不加volatile，编译器和处理器有可能对这三个指令进行重排序，比如①③②，从而使得线程B在第一次if判断时获得一个虽然不为null但其实并不完整的实例对象。

静态内部类 ：

public class Singleton {  
    private static class SingletonHolder {  
        private static final Singleton INSTANCE = new Singleton();  
    }  
    private Singleton (){}  
    public static final Singleton getInstance() {  
        return SingletonHolder.INSTANCE;  
    }  
}

利用Java类加载机制，保证线程安全和懒加载。具体而言，在Java中，类的加载和初始化是线程安全的，JVM会保证一个类在加载和初始化时由一个线程完成，因此，利用类加载机制可以确保单例实例的唯一性和线程安全性；相比饿汉式单例静态变量在外部类加载时就执行了实例化，静态内部类不受外部类加载的影响，只有在其自身第一次被访问时才会被加载和初始化，因此可以实现单例实例的懒加载。

时间复杂度和空间复杂度

时间复杂度函数O(f(n))在数学上的定义是，当n→∞，g(n)/f(n)=C，其中C为常数，g(n)为算法在问题规模为n的情况下需要执行的次数，则f(n)为其时间复杂度函数，记O(f(n))。

空间复杂度类似，反映的是算法执行过程中占用的内存空间的大小和问题规模n的关系。

关于复杂度要有一些常识性的概念，比如：

1. 二分查找时间复杂度：O(logn)，因为问题规模n每次都会减半，反过来如果题目要求时间复杂度O(logn)，要马上联想到是否可以用二分。
2. 二叉树遍历的时间复杂度：O(n)，因为树的每个节点只会被访问一次，无论是用迭代还是递归。
3. 最佳排序二维矩阵（每一行元素都按升序排列，每一列元素都按升序排列）查找的时间复杂度：O(n)。
4. 归并排序、快速排序的时间复杂度：O(nlogn)，代表一旦用到排序，最快也需要O(nlogn)的时间复杂度。
5. 递归需要函数调用栈的栈空间的使用（除非使用的是尾递归：递归调用是递归函数的最后一个操作，并且递归调用的返回值不需要额外处理直接返回，这种情况编译器会把递归优化为迭代，从而使用常数级别的栈空间），因此计算递归函数空间复杂度的时候需要考虑两点，一是每次递归所需空间，二是递归调用的最大深度，两者相乘便是该递归函数的空间复杂度。比如对于二分查找的递归解法，每次递归所需空间是O(1)，递归调用的最大深度也就是二分查找需要执行的次数为O(log n)，因此最终的空间复杂度是O(log n)。

Tips

1. 数组的长度：length，String的长度：length()，集合类的长度：size()。
2. 数组排序可以使用Arrays的sort方法，集合类排序可以使用Collections的sort方法。
3. String类的常用方法要牢记：比如字符遍历要先转化为字符数组toCharArray()，具体可查看Doc。
4. 在使用分治法（比如快速排序）解题计算middle值时，建议写middle=low+(high-low)/2而不是middle=(low+high)/2，因为后者有可能越界。
5. 对于int负数转正数，极值会越界，可以用long来存。
6. 位运算拿不准优先级的话记得多加括号。

结语

合格的面试官，会尽可能地通过面试去预判候选人未来的工作表现，而Coding面试其实是最接近工作能力展示的一种考察方式。因为通过Coding，可以反映出候选人的聪明程度、语言的熟练度、语言和计算机原理的理解、代码规范以及沟通能力等。 那么作为候选人，除了在面试前进行充分的刻意练习之外，在算法面试中也要做到有条不紊地切题：

1. 首先要全程保持心态稳定，慌张没有任何好处，同时也不要急于交卷，时刻注意边界和优化。
2. 充分地和面试官沟通题意和边界情况，为解题做准备。
3. 口述解题思路，在写代码前先给面试官讲自己的实现思路的好处是，如果你的解法注定有问题，面试官可能会提前指正并引导向正确的方向，从而避免浪费时间。此外，如果你对这道题很熟悉，能够想到多种解法，或者对你选择的解法的时间复杂度和空间复杂度足够明确，都可以提前讲出来，增加专业性，增加好感度。
4. 写代码，要有结构化思维，先把该定义的类、该声明的方法、该加的边界判断先写上，然后逐步实现完整逻辑。实现的过程中可以在心里或纸上做一些简单的验证，同时写的过程中或写完后记得要一定程度的格式化，方便阅读。最后把代码再过一遍，完成逻辑优化和代码简化。
5. 写测试用例验证结果，这个环节需要和面试官沟通清楚是否需要用例验证以及面试官是否会指定用例，要格外注意的同样是一些边界用例。

最后，对程序员来说，2024年，这显然不是最好的时代，但希望大家努力成为最好的自己吧！