Question

编程面试的时候，面试官通常对时间复杂度和空间复杂度都会有要求，并且一般情况下面试官更加关注时间复杂度。

降低时间复杂度的第一个方法是改用更加高效的算法。比如我们用动态规划解答面试题31连续子数组的最大和能够把时间复杂度降低到O（n），利用快速排序的Partition函数也能在O（n）时间解决面试题29数组中出现次数超过一半的数字和面试题30最小的k个数字。

降低时间复杂度的第二个方法是用空间换取时间。在解决面试题35第一个只出现一次的字符的时候，我们用数组实现一个简单的哈希表，于是用O（1）时间就能知道任意字符出现的次数。这种思路可以解决很多同类型的题目。另外，我们可以创建一个缓存保存中间的计算结果，从而避免重复的计算。面试题34丑数就是这方面的一个例子。在用递归的思路求解问题的时候，如果有重复的子问题，同样我们也可以通过保存求解子问题的结果来避免重复计算。更多关于递归的讨论请参考本书的2.4.2节及面试题9斐波那契数列。

值得注意的是，以空间换取时间并不一定都是可行的方案。我们要注意需要的辅助空间的大小，消耗太多的内存可能得不偿失。另外，我们还要关注问题的背景。如果面试题是有关嵌入式开发的，那对空间消耗就要格外留心，因为通常嵌入式系统的内存很有限。