数组array
数组是一种容器，其特征如下：
特征
- 有边界，数组有一个长度限制
- 数组成员类型是相同的(c/cpp, golang, rust)
- 地址连续，index连续
- 属于一种key-value的数据结构，数组的index相当于key，对应元素为value，数组可以看作为一种没有hash冲突的hash表,可以将数组看成一种特殊的map
- cache友好
- 不利于删除一个元素和添加一个元素
- 数组扩容方面不支持动态扩容
- 十分灵活的元素访问方式，支持根据index访问任何一个元素，不像链表必须从头开始，或者要获取到节点的地址
分类
长度是否固定
- 静态数组
- 动态数组
操作
创建数组
遍历
基本方式：
- 正向遍历
- 反向遍历
- 双向遍历（双指针）
数组的特征
重复元素
一个长度为n+1的数组，包含的数是1到n，其中有一个数至少出现了两次，请找到它。
例如，
输入：[3,2,4,2,1]
输出：2
缺少元素
How To: Solving the ‘Missing Number’ Question
1到n少了其中一个数据，找出缺失的这个数据。
异或的语句。
多数元素
多数元素是指一个元素在个数超过了一半。 https://medium.com/swlh/finding-the-majority-element-is-your-solution-efficient-enough-2a6b49a75cb8
第一步：找出出现次数最多的元素 第二步： 判断这个元素是否超过了半数
数组乘积
Solve the problem before coding it up
238. Product of Array Except Self
思路： 以此为例
Input: [1,2,3,4]
Output: [24,12,8,6]
正序： increaseArray = [1, 1, 2, 6]
increaseArray[0] = 1
increaseArray[1] = increaseArray[0]*data[1-0] =
反序： [24,12,4, 1]
decreaseArray[3] = 1
decreaseArray[2] = decreaseArray[3]*data[3-i]
两者相乘：
[24,12,8, 6]
子数组
Maximum Sum of Two Non-Overlapping Subarrays
数组合并
数组并不是数组
用数组表示堆。
字符串也是一种数组
光用数组并不能解决所有的问题
解决问题需要结合其他的数据结构
slide windows
题目类型分为两种：
- 固定子数组的长度，如找到最大值或最小值
- 不固定长度，如找到子数组之和等于指定的数值
leetcode-295 Find Median from Data Stream