数组有两个关键词:
- 线性表结构, 就是说元素之间只有前后关系
- 连续的内存空间,存储的是具有相同类型的数据
第二个特征决定了数组“随机访问”的能力,因为我们完全可以通过地址计算出下标对应的位置。比如:
a[i]_add = base_add + i * type_size
有利就有弊,也正是由于内存连续,所以数组的插入和删除是非常低效的,因为为了保持内存的连续,就意味着每次插入/删除都要伴随着大量的移动操作,平均负责度为o(n).
容器类在数组的基础上,封装了插入删除等操作,同时支持了动态扩容. 需要注意的是,如果实现知道数组的大小,最好提前指定容器大小,这样可以省掉多次的内存申请和数据搬移。
大多情况下的解题思路:
- 双指针(26, 27)
- DP
- 二分查找
题号 | 题目链接 | 答案链接 | 难度 | 完成度 |
---|---|---|---|---|
1 | 两数之和 | twoSum | easy | ✅ |
26 | 删除排序数组中重复项 | removeDuplicates | easy | ✅ |
27 | 移除元素 | removeElement | easy | ✅ |
35 | 搜索插入位置 | searchInsert | easy | ✅ |
53 | 最大子序和 | maxSubArray | easy | ✅ |
66 | 加一 | plusOne | easy | ✅ |
88 | 合并两个有序数组 | merge | easy | ✅ |
118 | 杨辉三角 | pascals_triangle | easy | ✅ |
119 | 杨辉三角2 | pascals_triangle_ii | easy | ✅ |
121 | 买卖股票的最佳时机 | best_time_to_buy_and_sell_stock | easy | ✅ |
122 | 买卖股票的最佳时机ii | best_time_to_buy_and_sell_stock_ii | easy | ✅ |
167 | 两数之和 II - 输入有序数组 | twoSum_ii | easy | ✅ |
169 | 求众数 | majorityElement | easy | ✅ |
189 | 旋转数组 | rotate | easy | ✅ |
11 | 盛最多水的容器 | maxArea | ✨✨ | ✅ |
283 | 移动零 | moveZeroes | ✨ | ✅ |
15 | 三数之和 | 3sum | medium | ✅ |
16 | 最接近的三数之和 | 3SumClosest | medium | ✅ |
39 | 组合总和 | combinationSum | medium | ✅ |
题号 | 题目链接 | 答案链接 | 难度 | 完成度 |
---|---|---|---|---|
-- | 剑指Offer(一):二维数组中的查找 | Find | ✨ | ✅ |
-- | 剑指Offer(六):旋转数组的最小数字 | minNumberInRotateArray | ✨ | ✅ |
-- | 剑指Offer(十三):调整数组顺序使奇数位于偶数前面 | reOrderArray | ✨ | ✅ |
-- | 剑指Offer(二十八):数组中出现次数超过一半的数字 | MoreThanHalfNum_Solution | ✨ | ✅ |
-- | 剑指Offer(三十):连续子数组的最大和 | -- | ✨ | ❌ |
-- | 剑指Offer(三十二):把数组排成最小的数 | PrintMinNumber | ✨ | ✅ |
-- | 剑指Offer(三十七):数字在排序数组中出现的次数 | GetNumberOfK | ✨ | ✅ |
-- | 剑指Offer(四十):数组中只出现一次的数字 | FindNumsAppearOnce | ✨ | ✅ |