【编程起跑线】03 数组和字符串

数组和字符串作为最基本的元素，涉及的知识点非常多，许多高级的应用如堆，栈，队列，动态规划等都可以基于数组，这一讲我们主要还是集中在数组本身性质的习题上。

更新历史

2019.08.05：编入新系列
2016.01.22：完成初稿

题目分类与解题策略

原本以为这一章内容不会很多，但是整理资料的时候发现，我把不少稍微有些『难度』的题目，也放到了这个类别下，不过也没有问题，万事开头难，熬过这一波就好了。

基本解题策略

判断元素是否出现：哈希表或者 bitset
统计元素出现次数：哈希表

重要知识点

越界问题
支持随机访问，修改读取 O(1)
插入删除 O(n)
哈希表，插入 O(1)，查找 O(1)
哈希表解决冲突的方式：链接法(chaining)和开放地址法(open addressing)

常见容器

Vector / ArrayList
HashSet, HashTable
Map / Dictionary

我们先来分析一下具体的题目类型，因为很多题目万变不离其宗，只要抓住解题思路，剩下的就是时间问题了（具体的题目列表在最后的附录中），下面是几个大类的问题及对应的思路：

次数统计

这类题目就是哈希表大显身手的时候了，比方说找唯一出现的字母或数字，或者是统计元素出现的次数，都可以用哈希表来快速完成。因为哈希表可以做到 O(1) 时间的检索，所以效率会很高。看一次这个分类下的题目就会发现，问题的突破口往往就是找到对应的建立哈希表的方式。

哈希表(Hash Table)几乎是最为重要的数据结构，主要用于基于“键(key)”的查找，存储的基本元素是键-值对(key-value pair)。逻辑上，数组可以作为哈希表的一个特例：键是一个非负整数。注意，通常哈希表会假设键是数据的唯一标识，相同的键默认表示同一个基本存储元素。

哈希表的本质是当使用者提供一个键，根据哈希表自身定义的哈希函数(hash function)，映射出一个下标，根据这个下标决定需要把当前的元素存储在什么位置。在一些合理的假设情况下，查找一个元素的平均时间复杂度是O(1)，插入一个元素的平摊(amortized)时间复杂度是O(1)。

当对于不同的键，哈希函数提供相同的存储地址时，哈希表就遇到了所谓的冲突(collision)。解决冲突的方式有链接法(chaining)和开放地址法(open addressing)两种。简单来说，链接法相当于利用辅助数据结构(比如链表)，将哈希函数映射出相同地址的那些元素链接起来。而开放地址法是指以某种持续的哈希方式继续哈希，直到产生的下标对应尚未被使用的存储地址，然后把当前元素存储在这个地址里。

通常而言，链接法实现相对简便，但是可能需要附加空间，并且利用当前空间的效率不如开放地址法高。开放地址法更需要合理设计的连续哈希函数，但是可以获得更好的空间使用效率。需要注意的是，过于频繁的冲突会降低哈希表的搜索效率，此时需要哈希表的扩张。

比较有特点的题目是：

特定模式

这个类型的题目比较多变化，比方说，找回文串，子串匹配，或者是两个数组中相差最小的两个元素，又或者是字符串按照一定规则变成数字。这类问题有一个特点，就是可以很容易想出暴力解法，但是暴力解法会有很多重复运算，效率不高，于是需要进一步进行优化。具体的优化方式有很多，比方说找回文串，如果比较复杂一点的 manacher 算法没办法保证百分百写对的话，那么以每个字符为中心开始延展的方式，也是不错的做法。

具体来说，就是一定要清楚地知道，具体在操作的元素是哪个，以及对应的匹配关系，一开始可能会比较慢，但是熟悉了之后就好了。比较有特点的题目是：

区间问题

区间问题的复杂性在于，需要处理多种情况，如果不事先想好的话，很容易出错。另外就是处理区间取数的问题，会涉及到一些动态规划的思想，当然，有些问题也可以用哈希表来解决。解决问题的关键在于，一定要意识到多种情况的可能，并且在代码中做对应的处理。比较有特点的题目是：

矩阵相关

矩阵就是二维数组，具体来说，难度在于，怎么处理好两个维度的问题。具体来说，就是要看题目中有没有给出一些明显的信息，比方说排好序。写关键代码的时候，一定要列好前条件和后条件，保证不出问题。比较有特点的题目是：

逻辑操作

这个类别包括的题目千奇百怪，理论上来说很难总结一个普适的规律，因为实际上就是根据特定的逻辑规则来进行操作。比方说以特定格式输出，旋转，排序，交换，合并，堆等等。因为变化太多，所以这里只能给出一个比较通用的建议：列出前条件后条件，注意每一步操作及可能带来的副作用，善于利用数据结构本身的能力。比较有特点的题目有：