Arrays

数组要点

数组可以说是最简单的一种数据结构，它占据一块连续的内存并按照顺序存储数据。创建数组时，我们需要首先制定数组的容量大小，然后根据大小分配内存。即使只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分利用。

由于数组中的内存是连续的，于是可以根据下标在O(1)时间读/写任何元素，因此时间效率很高。可以根据数组时间效率高的优点，用数组来实现简单的哈希表：把数组的下标设为哈希表的键值Key，而把数组中的每一个元素设为哈希表的值Value，如此实现Key-Value配对。

为了解决数组空间效率不高的问题，人们又设计实现了多种动态数组，如STL中的vector。为了避免浪费，先为数组开辟较小的空间，然后往数组中添加数据。当数据的数目超过数组的容量时，我们再重新分配一块儿更大的空间（STL的vector每次扩充容量时，新的容量都是前一次的两倍），把之前的数据复制到新的数组中，再把之前的内存释放，这样就能减少内存的浪费。注意到每一次扩充数组容量的时间效率是O(n)，对时间性能有负面影响，因此要尽量减少数组扩容的次数。

在C里，数组和指针是相互关联又有区别的两个概念。声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。C中，当数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。用sizeof()求大小时从(数组的大小*类型大小)变成(指针的大小4)。

例题：输出20,4,4。

int get_size(int data[]) {
	return sizeof(data);
}
int main(){

	int data1[] = {1,2,3,4,5};
	int size1 = sizeof(data1);	// 5 * 4
	int* data2 = data1;
	int size2 = sizeof(data2);	// 4
	int size3 = get_size(data1);	// 4
	cout << size1 << "," << size2 << "," << size3;
}

引用不能放进数组。
函数体内定义的内置数组，其元素无初始化。
不允许数组直接复制和赋值。
数组的长度是固定的。
数组的size类型为size_t。

STL中的vector

STL中的vector是动态数组。详细内容见这里。

leetcode相关题目

注意是否要求在位、数组内是否允许重复、数组是否已排序、数组内数值的范围、还有一些边界条件，常常用到unordered_set/unordered_map，有时需要以数字的每一位为单位来考虑，有的题目常用几个指针向中间逼近的思路，有的将数据中的一位或几位作为标识符，有的是左右各扫一遍在每一位取两者的最大值，有的需要利用二进制的性质。还要注意活用索引和指针，遍历的同时也可以操作其他位置。
数组题目的套路还是比较少，毕竟只是一个数据结构，常常要对具体问题想一些比较特殊有针对性的解法。
Remove Duplicates from Sorted Array
Remove Duplicates from Sorted Array II
Search in Rotated Sorted Array
Search in Rotated Sorted Array II
Median of Two Sorted Arrays
Longest Consecutive Sequence
Two Sum
3Sum
3Sum Closest
4Sum
Remove Element
Next Permutation
Permutation Sequence
Valid Sudoku
Trapping Rain Water
Rotate Image
Plus One
Climbing Stairs
Gray Code
Set Matrix Zeroes
Gas Station
Candy
Single Number
Single Number II
Maximum Product Subarray
Move Zeros
Two Pointers | Intersection of Two Arrays
Two Pointers | Intersection of Two Arrays II

[1] 剑指Offer
[2] leetcode
[3] C++ Primer 4th edition