数据结构与算法（数组）~ 介绍数组以及力扣上几道数组题目的方法和套路

1，数组的数据结构 【没啥好说的哈哈哈，可以说一下动态数组哈哈哈】

动态数组：（可以动态改变数组的长度）

（1）基本实现（组成）：内部有数组的引用（开始是初始化指向为某个定长的数组），当需要动态改变数组长度时，其实是定义另外一个长度的定长数组，把原先数组的引用指向新创建的数组（然后把老数组的数据，进行遍历复制到新数组中）。

自己动手实现：定义了一个动态数组（含有数组引用和数组长度）:

（2）数组主要的功能（增删改查）：定义一些接口方法

（3）过程中进行重构链表，将 增删改查 或者一些通用的接口或者属性封装到外部抽象类或者接口（方便设计给其他类用这样子）：

（整个版本一的链表过程如此）

过程中增删改查实现的具体代码就 略。。。

● 增加：可以在任意一个位置进行增加结点

● 删除：可以在任意一个位置进行删除结点

● 修改：可以在任意一个位置进行修改结点

● 查找：可以查找任意一个位置的结点

✿ 升级版本（实现自动缩容的功能、实现优化利于空间，定义一个指针循环利用数组的空间）

2，数组的力扣算法题：

总结一些小套路吧 （没有通用的套路，就讲一下方法哈）：

（1）1_两数之和 的方法 ：

方法一：暴力枚举（两层循环）

方法二：哈希表 【数组元素， 下标】

（2）接下来的几道题可以直接看文章（它们具有某种共性）：

《 双指针（使用题目：求子数组（可能是连续的或者是数组中某两个或某三个之和（积等等）等于某个值）特点分析【切记每道题目的分析都要切合题意】》

（3）121_买卖股票的最佳时机：
方法一：一次遍历（在此遍历的过程中不断的更新找到最低点（最低点作为买点）， 后续的非最低点，则考虑是否可以作为卖点）

（4）4_寻找两个正序数组的中位数:

方法一：先从小到大合并，然后再找中间的那个数。