1、数组
- 数组是由相同类型的元素组成的数据集合，并且占据一块连续的内存，按照顺序存储数据。
1.1、数组的特性：
- 数组元素通过下标获取数据
- 数组对象初始化时，需要先指定数组容量大小，并根据容量大小分配内存。
- 缺点：需要为所有的数据预先分配内存，可能存在空闲的区域没有得到充分利用。
1.2、动态数组
- 先为数组分配较小的内存空间，然后在需要的时候，在数组中添加新的数据。
- 当容量不足时，需要重新分配一块更大的空间，要把之前的数据复制到新的数组中，再把之前的内存释放。
- 缺点：数据拷贝时，需要进行大量的额外操作。
2、指针
- 能定位数据容器中（也就是内存中）某个数据的手段。也就是数据的句柄或者地址。
2.1、双指针
- 双指针是一种解题方法
- 方向相反的双指针经常用来求排序数组中的两个数字之和。通常分别指向数组的首位两端，根据结果值对两端的指针进行向中间移动。
- 方向相同的双指针通常用来求正数数组中子数组的和或乘积。
3、LCR 006 两数之和
3.1、题目信息：
- https://leetcode.cn/problems/kLl5u1/description/
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。示例 1：
输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。示例 2：
输入：numbers = [2,3,4], target = 6
输出：[0,2]示例 3：
输入：numbers = [-1,0], target = -1
输出：[0,1]
3.2、解题思路
- 输入一个整数数组和一个目标整数，要求从数组中找出两个数，要求他们的和等于目标整数，返回两个元素的下标数组
1）、暴力解法
- 双层for循环，遍历数组获得整数元素，然后遍历其他元素，判断他们的和是否等于目标值
- 时间复杂度n的平方，没有使用到数组元素是升序排序的特性
- 代码简单，不实现
2）、哈希表解法
- 遍历数组元素，遍历的过程中，判断目标值与遍历元素的差值，判断差值是否在哈希表中，如果存在则返回下标数组
- 如果不存在，则将当前遍历的元素和下标值，保存到哈希表中
vector<int> twoSum(vector<int> &numbers, int target)
{vector<int> res;std::map<int, int> map;for (int i = 0; i < numbers.size(); i++){int num = target - numbers[i];if (map.find(num) != map.end()) {res.push_back(map[num]);res.push_back(i);break;}map[numbers[i]] = i;}return res;
}
3）、双指针解法
- 定义两个下标，从数组的两端开始往中间遍历
- 如果遍历到的两个元素的和等于目标值，则直接返回，如果两元素和大于目标值，则right角标左移，否则left角标右移
vector<int> twoSum(vector<int> &numbers, int target)
{vector<int> res;int left = 0;int right = numbers.size() - 1;while (left < right && target != (numbers[left] + numbers[right])){if (numbers[left] + numbers[right] < target){left++;}else{right--;}}res.push_back(left);res.push_back(right);return res;
}
4、总结
- 数组特性，具有相同数据类型的数据集合，在内存中按顺序连续存储，数组对象就是数据的指针，可通过下标获取到数组中元素的值
- 数组优缺点：可通过数组索引下标直接获取元素值，在数组尾部添加数据，插入与删除数据需要进行数据移动； 数组使用前需要预先分配内存，有可能有些内存没有使用到。
- 动态内存，刚开始分配一个小容量的内存，当数据量增加时进行扩容，需要将原数据拷贝到新的数组中。
- 指针概念，就是可以从内存中获取数据的方式
- 双指针，是一种解题思路，分为相向指针和相反指针。
- map数据结构使用，查找是否存在某个值使用find方法
)
