数组（Array）
数组最值钱的性质只有一个：下标访问是
O(1)。很多双指针、前缀和、滑动窗口，其实都建立在这个性质上。
核心思路
数组是一种线性数据结构，用一段连续的内存空间来存储一组具有相同类型的数据。
核心特点
- 随机访问：通过索引可以 O(1) 时间访问任意元素
- 连续存储：元素在内存中连续存放
- 固定大小：静态数组创建后大小固定（动态数组可扩容）
- 类型统一：所有元素类型相同
基本操作
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 访问 | O(1) | 通过索引直接访问 |
| 搜索 | O(n) | 需要遍历（有序数组可用二分O(logn)） |
| 插入 | O(n) | 需要移动后续元素 |
| 删除 | O(n) | 需要移动后续元素 |
| 末尾插入 | O(1) | 动态数组可能需要扩容 |
内存地址计算
地址(a[i]) = 基地址 + i × 元素大小
Go 代码
Go 实现
// 1. 创建数组/切片
arr := [5]int{1, 2, 3, 4, 5} // 固定数组
slice := []int{1, 2, 3, 4, 5} // 切片（动态）
// 2. 访问
element := slice[0]
// 3. 添加元素
slice = append(slice, 6)
// 4. 遍历
for i, v := range slice {
fmt.Printf("index: %d, value: %d\n", i, v)
}双指针模板
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
slow := 0
for fast := 1; fast < len(nums); fast++ {
if nums[fast] != nums[slow] {
slow++
nums[slow] = nums[fast]
}
}
return slow + 1
}数组变体
1. 动态数组（Dynamic Array）
- 特点：大小可变，自动扩容
- 扩容策略：通常按一定比例扩容
- 平摊复杂度：插入平摊 O(1)
3. 稀疏数组（Sparse Array）
- 大部分元素为0或默认值
- 使用字典或特殊结构存储非零元素
怎么识别数组题
- 给你一段连续序列，要求原地修改。
- 要求随机访问、双指针、滑动窗口。
- 问题本质是区间统计、区间更新或顺序扫描。
常用技巧
经典题目
基础题
- 两数之和 - LeetCode 1
- 删除排序数组中的重复项 - LeetCode 26
- 合并两个有序数组 - LeetCode 88
双指针
滑动窗口
- 最大子数组和 - LeetCode 53
- 无重复字符的最长子串 - LeetCode 3
二维数组
易错点
数组题常见失误不是算法不会，而是边界和原地覆盖顺序写反了。
- 原地修改时先想清楚读指针和写指针各负责什么。
- 切片扩容可能触发底层复制，不要错误共享旧引用。
- 二维数组要统一行列含义，别把
i/j写反。 - 滑动窗口里窗口收缩和扩张条件要成对出现。
优缺点
优点
- ✅ 随机访问效率高 O(1)
- ✅ 内存连续，缓存友好
- ✅ 实现简单，使用广泛
缺点
- ❌ 插入删除效率低 O(n)
- ❌ 大小固定（静态数组）
- ❌ 内存连续要求高，可能导致空间浪费
应用场景
- 需要频繁随机访问：查表、索引
- 数据量已知且固定：配置数据、查找表
- 顺序存储的数据：时间序列、日志
- 实现其他数据结构：栈、队列、堆的底层实现