边刷边学（一）—深入浅出理解数组

type

status

date

slug

summary

💢什么是数组？

一种线性数据结构（Linear Data Structure），它在内存中按连续空间（contiguous memory）存储一组相同类型的数据元素。每个元素都可以通过一个下标（index）直接访问，这使得数组在随机访问上的性能极为高效。

而这个老生常谈的概念中，其实隐藏着一个需要被掌握的细节：正是因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。数组的元素是不能删的，只能覆盖。

😇数组的底层实现？

数组的精髓在于它的地址计算方式。假设一个整型数组在内存中从地址base开始，每个元素占用sizeof(int)字节，若要访问第i个元素，其内存地址可通过以下公式计算：

这种通过偏移量（offset）直接定位的机制，使得数组能以常数时间（O(1))完成随机访问。

而这也是链表等结构无法做到的性能优势。

然而，连续内存布局也带来一些限制：

插入或删除中间元素需要移动大量数据，复杂度为 O(n)；

扩容困难，需要重新分配一块更大的连续空间。

🫥内存管理

数组在底层存储上直接操作堆（Heap）或栈（Stack）内存。

在 C/C++ 中：

静态数组常分配在栈上，如 int a[10];
动态数组（malloc 或 new 分配）存放于堆上，需手动释放内存。

在 Java/Python 中：

数组对象始终在堆上分配，由垃圾回收机制自动管理。

由于数组内存连续，访问局部元素时会充分利用CPU缓存局部性（Cache locality），因此在循环中访问数组往往比链表更高效。

🤨来点儿小题

LC704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

示例 2:

提示：

你可以假设 nums 中的所有元素是不重复的。

n 将在 [1, 10000]之间。

nums 的每个元素都将在 [-9999, 9999]之间。

思路：

该题目给定了数组的两个关键信息：1）有序的（升序）整型数组；2）所有元素是不重复；实际上这两个信息也是使用二分查找的必要条件。

题解：

LC27.移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

题解：

两个方法，由于题目只要求了空间复杂度在O(1)，所以可以不那么优雅地两次for循环暴力求解，原因是上面提到的，数组在内存空间的地址是连续的，无法直接删除某个元素，因此需要一个for循环遍历数组元素，第二个for循环更新数组。

这里用稍微优雅一点的方法来解，快慢指针。

LC977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

示例 2：

思路：

不那么优雅的方式就是直接暴力求解，所有元素平方后再排序（nums.sort)即可；相对优雅一点的解法是采用双指针，因为原数组是按非递减顺序排列的，那么我们可以知道平方对其顺序产生的影响就是负数会变大，因此顺序改变的情况一定出现在数组两端，所以我们可以设计双指针来解决这个问题：

题解：

LC209.长度最小的连续子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

题解：

暴力解法：两个for循环，遍历求出来最短的，时间复杂度显然O(n^2)

滑动窗口：本质上也是两个指针，在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成了一个不断搜索区间的过程。二滑动窗口则需要用一个for循环来完成这个操作。

在本题中实现滑动窗口，主要确定如下三点：

窗口内是什么？

如何移动窗口的起始位置？

如何移动窗口的结束位置？

窗口就是满足其和 ≥ s 的长度最小的连续子数组。

窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

题解：

时间复杂度O(n)，空间复杂度O(1)

区间和

注：本题需要用ACM格式

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

输出示例

思路：老规矩，先想想暴力解法，给一个区间，然后我把这个区间的和都累加一遍不就得了。但是这样做会超时☹️，因为实际上每一次找这个区间，都会触发对数组的查询，如果我查询m次，每次查询的范围都是从0 到 n - 1那么该算法的时间复杂度是 O(n * m) m 是查询的次数，如果查询次数非常大的话，这个时间复杂度也是非常大的。

其实一般在涉及到区间计算的时候，会用到前缀和，这是一个很方便也相对优雅的方式：

例如，我们要统计 vec[i] 这个数组上的区间和。

我们先做累加，即 p[i] 表示下标 0 到 i 的 vec[i] 累加之和。

如果我们想统计，在vec数组上下标 2 到下标 5 之间的累加和，那用 p[5] - p[1] 就可以了。这样就降低了“查询”这一步骤带来的时间复杂度。

题解：

LC59. 螺旋矩阵II

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路：这个题本身不难，确定好边界即可

题解：