数组（Array）是一种基础的线性数据结构，用于存储固定大小的同类型元素集合。所有元素在内存中是连续存储的，每个元素都可以通过索引进行访问。数组是编程中最基本的数据结构之一，也是许多高级算法和数据结构的基础。
数组内存结构示意：
索引: 0 1 2 3 4 5
┌──────┬──────┬──────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │
└──────┴──────┴──────┴──────┴──────┴──────┘
内存地址: 1000 1004 1008 1012 1016 1020 (假设每个元素4字节)
↑ ↑
基地址 随机访问: O(1)
多维数组结构示意：
二维数组 (3×4):
列0 列1 列2 列3
行0 [ 1 ] [ 2 ] [ 3 ] [ 4 ]
行1 [ 5 ] [ 6 ] [ 7 ] [ 8 ]
行2 [ 9 ] [10 ] [11 ] [12 ]
内存中的存储方式 (行优先):
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
- 一维数组：线性排列的元素集合
- 多维数组：矩阵形式的数据组织
- 动态数组：可以自动扩容的数组实现
- 静态数组：固定大小的数组
优点：
- 快速访问：O(1)时间复杂度的随机访问
- 内存连续：缓存友好的内存布局
- 简单直观：易于理解和使用
缺点：
- 大小固定：静态数组无法动态调整大小
- 插入删除低效：需要移动大量元素
- 内存浪费：可能分配过多未使用的空间
概述：
- 将数组中的元素顺序完全反转。
- 使用双指针技术，一个在头部，一个在尾部。
算法过程示意：
初始数组: [1, 2, 3, 4, 5, 6]
↑ ↑
left right
步骤1: 交换 1 和 6
[6, 2, 3, 4, 5, 1]
↑ ↑
left+1 right-1
步骤2: 交换 2 和 5
[6, 5, 3, 4, 2, 1]
↑ ↑
left+2 right-2
步骤3: 交换 3 和 4
[6, 5, 4, 3, 2, 1]
↑
left ≥ right (停止)
结果: [6, 5, 4, 3, 2, 1]
核心思想：
- 左右指针同时向中间移动
- 交换对应位置的元素
- 当指针相遇或交叉时停止
应用：
- 字符串反转
- 数据预处理
- 算法中的辅助操作
实现文件：
reverse/- 多语言实现
概述：
- 将数组向左或向右旋转k个位置。
- 可以使用三次翻转法实现原地旋转。
算法过程示意 (向右旋转2位)：
初始数组: [1, 2, 3, 4, 5, 6, 7], k=2
第1步 - 翻转整个数组:
[7, 6, 5, 4, 3, 2, 1]
第2步 - 翻转前k个元素 (前2个):
[6, 7, 5, 4, 3, 2, 1]
↑ ↑
翻转后
第3步 - 翻转后n-k个元素 (后5个):
[6, 7, 1, 2, 3, 4, 5]
↑─────────────↑
翻转后
结果: [6, 7, 1, 2, 3, 4, 5]
核心思想：
- 翻转整个数组
- 翻转前k个元素
- 翻转后n-k个元素
应用：
- 循环队列实现
- 字符串轮转
- 数组元素重排
实现文件：
rotate/- 多语言实现
概述：
- 移除数组中的重复元素，只保留唯一的元素。
- 多种实现方式：哈希表、双指针、排序等。
哈希表法过程示意：
初始数组: [1, 2, 2, 3, 4, 4, 5]
遍历过程:
┌─────────────────┬─────────────────┬─────────────────┐
│ 当前元素 │ 哈希表状态 │ 结果数组 │
├─────────────────┼─────────────────┼─────────────────┤
│ 1 │ {1} │ [1] │
│ 2 │ {1,2} │ [1,2] │
│ 2 │ {1,2} ✗已存在 │ [1,2] │
│ 3 │ {1,2,3} │ [1,2,3] │
│ 4 │ {1,2,3,4} │ [1,2,3,4] │
│ 4 │ {1,2,3,4} ✗ │ [1,2,3,4] │
│ 5 │ {1,2,3,4,5} │ [1,2,3,4,5]│
└─────────────────┴─────────────────┴─────────────────┘
结果: [1, 2, 3, 4, 5]
核心思想：
- 哈希表法：记录已见过的元素
- 双指针法：适用于已排序数组
- 排序法：先排序再去重
应用：
- 数据清洗
- 统计分析
- 缓存优化
实现文件：
unique/- 多语言实现
概述：
- 找到数组中连续子数组的最大和。
- 经典的Kadane算法，动态规划思想。
Kadane算法过程示意：
初始数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
遍历过程:
┌────────┬────────────┬─────────────┬──────────────────┐
│ 元素 │ current_sum│ max_sum │ 说明 │
├────────┼────────────┼─────────────┼──────────────────┤
│ -2 │ -2 │ -2 │ 初始值 │
│ 1 │ 1 │ 1 │ max(-2+1,1)=1 │
│ -3 │ -2 │ 1 │ max(1-3,-3)=-2 │
│ 4 │ 4 │ 4 │ max(-2+4,4)=4 │
│ -1 │ 3 │ 4 │ max(4-1,-1)=3 │
│ 2 │ 5 │ 5 │ max(3+2,2)=5 │
│ 1 │ 6 │ 6 │ max(5+1,1)=6 │
│ -5 │ 1 │ 6 │ max(6-5,-5)=1 │
│ 4 │ 5 │ 6 │ max(1+4,4)=5 │
└────────┴────────────┴─────────────┴──────────────────┘
最大和: 6
子数组: [4, -1, 2, 1] (从下标3到6)
核心思想：
- 维护当前子数组和
- 维护全局最大和
- 当前和为负数时重新开始
应用：
- 股票最大收益
- 信号处理
- 数据分析
实现文件：
maximum-subarray/- 多语言实现
概述：
- 在数组中找到两个数，使其和等于目标值。
- 使用哈希表实现O(n)时间复杂度。
算法过程示意 (target=9)：
初始数组: [2, 7, 11, 15], target=9
遍历过程:
┌────────┬────────────────────┬──────────────────────┐
│ 元素 │ 补数=target-元素 │ 哈希表状态 │
├────────┼────────────────────┼──────────────────────┤
│ 2 │ 9-2=7 │ {} → {2:0} │
│ 7 │ 9-7=2 ✓存在! │ 返回 [0,1] │
└────────┴────────────────────┴──────────────────────┘
完整过程示意:
步骤1: 遍历到2, 哈希表={}, 7不在表中, 存入{2:0}
步骤2: 遍历到7, 哈希表={2:0}, 2在表中, 返回[0,1]
结果: [0, 1] (元素2和7, 下标0和1)
核心思想：
- 遍历数组时记录已见过的数
- 检查目标值与当前数的差值
- 利用哈希表快速查找
应用：
- 配对问题
- 数据匹配
- 游戏开发
实现文件：
two-sum/- 多语言实现
概述：
- 将数组中的所有零移动到末尾。
- 保持非零元素的相对顺序。
双指针法过程示意：
初始数组: [0, 1, 0, 3, 12, 0, 5]
slow指针(写位置)和fast指针(读位置):
初始: [0, 1, 0, 3, 12, 0, 5]
↑
slow=fast=0
fast=1: [1, 1, 0, 3, 12, 0, 5] 非零! 写入slow=0位置
↑ ↑
slow=1 fast=1
fast=2: [1, 1, 0, 3, 12, 0, 5] 为零, 跳过
↑ ↑
slow=1 fast=2
fast=3: [1, 3, 0, 3, 12, 0, 5] 非零! 写入slow=1位置
↑ ↑
slow=2 fast=3
fast=4: [1, 3, 12, 3, 12, 0, 5] 非零! 写入slow=2位置
↑ ↑
slow=3 fast=4
fast=5: 为零, 跳过
fast=6: [1, 3, 12, 5, 12, 0, 5] 非零! 写入slow=3位置
↑ ↑
slow=4 fast=6
最后填充零: [1, 3, 12, 5, 0, 0, 0]
结果: [1, 3, 12, 5, 0, 0, 0]
核心思想：
- 使用写指针记录非零元素位置
- 先将所有非零元素移到前面
- 将剩余位置填充为零
应用：
- 数据清理
- 内存压缩
- 算法优化
实现文件：
move-zeroes/- 多语言实现
概述：
- 将两个已排序的数组合并为一个有序数组。
- 从尾部向前填充，避免覆盖未处理元素。
算法过程示意：
nums1 = [1, 2, 3, 0, 0, 0], m=3
nums2 = [2, 5, 6], n=3
初始化指针:
i = m-1 = 2 (nums1有效元素末尾)
j = n-1 = 2 (nums2末尾)
k = m+n-1 = 5 (结果位置)
步骤1: nums1[2]=3 vs nums2[2]=6, 6更大
nums1[5]=6, j=1, k=4
[1, 2, 3, 0, 0, 6]
步骤2: nums1[2]=3 vs nums2[1]=5, 5更大
nums1[4]=5, j=0, k=3
[1, 2, 3, 0, 5, 6]
步骤3: nums1[2]=3 vs nums2[0]=2, 3更大
nums1[3]=3, i=1, k=2
[1, 2, 3, 3, 5, 6]
步骤4: nums1[1]=2 vs nums2[0]=2, 相等选nums2
nums1[2]=2, j=-1, k=1
[1, 2, 2, 3, 5, 6]
步骤5: j<0, nums2已用完, 剩余nums1元素已在正确位置
结果: [1, 2, 2, 3, 5, 6]
核心思想：
- 使用三个指针：分别指向两个数组的末尾和结果位置
- 比较两个数组的元素，选择较大的放入结果
- 处理剩余元素
应用：
- 归并排序
- 数据合并
- 外部排序
实现文件：
merge-sorted-array/- 多语言实现
- 数据清洗：去重、过滤、格式化
- 数据转换：重排、旋转、反转
- 数据合并：多个数据源的整合
- 排序算法：快速排序、归并排序的基础
- 搜索算法：二分搜索的前提
- 动态规划：状态存储和转移
- 缓冲区管理：固定大小的数据存储
- 队列实现：循环队列、双端队列
- 缓存系统：LRU缓存的数据存储
- 信号处理：时序数据分析
- 图像处理：像素数据存储
- 统计分析：数据集处理
技术分类示意：
双指针技术
├── 相向双指针 (头尾向中间移动)
│ └── 应用: 数组反转、两数之和(已排序)
│
│ 示意: 数组反转
│ [1, 2, 3, 4, 5, 6]
│ ↑ ↑
│ left right
│ └──────────────┘
│ 交换后相向移动
│
├── 同向双指针 (快慢指针)
│ └── 应用: 滑动窗口、去重
│
│ 示意: 去重
│ [1, 1, 2, 2, 3, 3]
│ ↑ ↑
│ slow fast
│ ↓
│ [1, 2, 3, ...]
│ ↑ ↑
│ slow fast
│
└── 分离双指针 (读写分离)
└── 应用: 移动零、合并数组
示意: 移动零
[0, 1, 0, 3, 12]
↑ ↑
write read
↓
[1, 3, 12, 0, 0]
↑ ↑
write read
- 去重操作：快速判断重复
- 查找配对：两数之和、三数之和
- 频率统计：元素出现次数
- 原地排序：减少空间复杂度
- 部分排序：只排序需要的部分
- 稳定排序：保持相等元素的相对顺序
| 操作 | 最好 | 平均 | 最坏 |
|---|---|---|---|
| 访问 | O(1) | O(1) | O(1) |
| 搜索 | O(1) | O(n) | O(n) |
| 插入 | O(1) | O(n) | O(n) |
| 删除 | O(1) | O(n) | O(n) |
- 原地操作：O(1)额外空间
- 哈希表辅助：O(n)额外空间
- 递归调用：O(log n)到O(n)栈空间
每种算法都提供了多种编程语言的实现：
- C：指针操作，手动内存管理
- Java：面向对象，集合框架
- Go：切片操作，简洁语法
- JavaScript：动态数组，灵活操作
- Python：列表操作，丰富库函数
- Rust：安全内存，零成本抽象
- 基础操作：访问、遍历、修改
- 简单算法：反转、旋转、去重
- 进阶算法：最大子数组、两数之和
- 综合应用：合并、移动零、复杂问题
- 边界条件：空数组、单元素数组
- 时间复杂度：选择最优算法
- 空间复杂度：尽量原地操作
- 代码规范：清晰的变量命名和注释