数组矩阵理论基础

普通数组理论基础

1. 数组的基本概念

**数组（Array）**是一种线性数据结构，由相同类型的元素按一定顺序排列而成，通过索引访问元素。

1.1 基本术语

• 索引（Index）：数组中元素的位置，通常从0开始
• 元素（Element）：数组中存储的数据
• 长度（Length）：数组中元素的数量
• 一维数组：线性排列的数组
• 二维数组（矩阵）：按行和列排列的数组

1.2 数组的特点

• 连续内存：数组元素在内存中连续存储
• 随机访问：通过索引可以在O(1)时间内访问任意元素
• 固定大小：数组大小在创建时确定（C++中vector是动态数组）
• 元素覆盖：数组元素不能直接删除，只能覆盖

示例：

一维数组：[1, 2, 3, 4, 5] 索引： 0 1 2 3 4 二维数组（矩阵）： [1, 2, 3] [4, 5, 6] [7, 8, 9] 行索引：0, 1, 2 列索引：0, 1, 2

2. 数组的基本操作

2.1 数组的遍历

一维数组遍历：

// 方式1：索引遍历for(inti=0;i<nums.size();i++){// 访问 nums[i]}// 方式2：范围遍历for(intnum:nums){// 访问 num}

二维数组遍历：

// 遍历二维数组for(inti=0;i<matrix.size();i++){for(intj=0;j<matrix[i].size();j++){// 访问 matrix[i][j]}}

2.2 数组的修改

重要特性：

• 数组元素不能直接删除，只能覆盖
• 删除操作需要将后续元素前移

示例：

// 删除索引为index的元素voidremoveElement(intarr[],int&size,intindex){if(index<0||index>=size){return;// 索引无效}// 将后续元素前移for(inti=index;i<size-1;i++){arr[i]=arr[i+1];}size--;// 减少数组大小}

3. 前缀和（Prefix Sum）

3.1 前缀和的基本概念

前缀和是数组中前i个元素的和，用于快速计算区间和。

定义：

• prefix[i] = arr[0] + arr[1] + ... + arr[i]
• 区间[a, b]的和 =prefix[b] - prefix[a-1]（a > 0）
• 区间[0, b]的和 =prefix[b]

示例：

原数组：[1, 2, 3, 4, 5] 前缀和：[1, 3, 6, 10, 15] 计算区间[1, 3]的和： prefix[3] - prefix[0] = 10 - 1 = 9 验证：2 + 3 + 4 = 9 ✓

3.2 前缀和的构造

核心思路：

• 遍历数组，累加元素
• 将累加结果存入前缀和数组

模板代码：

// 构造前缀和数组vector<int>prefix(n);intpresum=0;for(inti=0;i<n;i++){presum+=arr[i];prefix[i]=presum;}

3.3 区间和查询

适用场景：多次查询数组的区间和

核心思路：

• 使用前缀和数组快速计算区间和
• 时间复杂度：O(1)（查询），O(n)（预处理）

模板代码：

// LeetCode 58. 区间和#include<iostream>#include<vector>usingnamespacestd;intmain(){intn,a,b;cin>>n;vector<int>vec(n);// 输入数组vector<int>p(n);// 前缀和数组intpresum=0;// 构造前缀和数组for(inti=0;i<n;i++){scanf("%d",&vec[i]);presum+=vec[i];p[i]=presum;}// 查询区间和while(~scanf("%d%d",&a,&b)){intsum;if(a==0){sum=p[b];// 区间[0, b]的和}else{sum=p[b]-p[a-1];// 区间[a, b]的和}printf("%d\n",sum);}return0;}

关键点：

• 前缀和数组：p[i]表示前i+1个元素的和
• 区间和计算：[a, b]的和 =p[b] - p[a-1]
• 边界处理：当a=0时，直接使用p[b]
• 时间复杂度：预处理O(n)，查询O(1)

4. 矩阵（二维数组）操作

4.1 矩阵的基本概念

**矩阵（Matrix）**是二维数组，由行和列组成。

基本操作：

• 访问元素：matrix[i][j]（第i行第j列）
• 行数：matrix.size()
• 列数：matrix[0].size()

4.2 矩阵的遍历

按行遍历：

for(inti=0;i<matrix.size();i++){for(intj=0;j<matrix[i].size();j++){// 访问 matrix[i][j]}}

按列遍历：

for(intj=0;j<matrix[0].size();j++){for(inti=0;i<matrix.size();i++){// 访问 matrix[i][j]}}

4.3 螺旋矩阵

适用场景：按螺旋顺序遍历或生成矩阵

核心思路：

• 使用循环不变量：每次操作的方法一致（左闭右开）
• 按圈遍历：从外圈到内圈
• 处理边界：单行或单列的特殊情况

模板1：螺旋矩阵（遍历）

适用场景：按螺旋顺序遍历矩阵并输出元素

模板代码：

// LeetCode 54. 螺旋矩阵classSolution{public:vector<int>spiralOrder(vector<vector<int>>&matrix){vector<int>ans;intm=matrix.size();intn=matrix[0].size();intstartx=0,starty=0;// 起始位置intoffset=1;// 每圈的偏移量intloop=min(m,n)/2;// 循环圈数// 处理单行或单列if(m==1){returnmatrix[0];}if(n==1){for(intk=0;k<m;k++){ans.push_back(matrix[k][0]);}returnans;}// 按圈遍历（左闭右开）while(loop--){inti=startx,j=starty;// 第一行：从左到右for(;j<n-offset;j++){ans.push_back(matrix[i][j]);}// 最后一列：从上到下for(;i<m-offset;i++){ans.push_back(matrix[i][j]);}// 最后一行：从右到左for(;j>starty;j--){ans.push_back(matrix[i][j]);}// 第一列：从下到上for(;i>startx;i--){ans.push_back(matrix[i][j]);}startx++;starty++;offset++;}// 处理剩余的单行或单列if(min(m,n)%2==1){if(m<=n){// 剩余单行for(intjj=starty;jj<n-offset+1;jj++){ans.push_back(matrix[startx][jj]);}}else{// 剩余单列for(intii=startx;ii<m-offset+1;ii++){ans.push_back(matrix[ii][starty]);}}}returnans;}};

关键点：

• 循环不变量：左闭右开
• 四个方向：右→下→左→上
• 边界处理：单行或单列的特殊情况
• 时间复杂度：O(m × n)，空间复杂度：O(1)

模板2：螺旋矩阵II（生成）

适用场景：生成一个n×n的螺旋矩阵

模板代码：

// LeetCode 59. 螺旋矩阵IIclassSolution{public:vector<vector<int>>generateMatrix(intn){vector<vector<int>>vec(n,vector<int>(n));intstartx=0,starty=0;// 起始位置intoffset=1;// 每圈的偏移量intcount=1;// 填充的数字intcir=n/2;// 循环圈数intmid=n/2;// 中间位置// 按圈填充（左闭右开）while(cir--){inti=startx,j=starty;// 第一行：从左到右for(;j<n-offset;j++){vec[i][j]=count++;}// 最后一列：从上到下for(;i<n-offset;i++){vec[i][j]=count++;}// 最后一行：从右到左for(;j>startx;j--){vec[i][j]=count++;}// 第一列：从下到上for(;i>starty;i--){vec[i][j]=count++;}startx++;starty++;offset++;}// 处理中间元素（n为奇数时）if(n%2){vec[mid][mid]=count;}returnvec;}};

关键点：

• 循环不变量：左闭右开
• 四个方向填充：右→下→左→上
• 中间元素：n为奇数时需要单独处理
• 时间复杂度：O(n²)，空间复杂度：O(n²)

4.4 矩阵的统计操作

适用场景：统计矩阵的行和、列和等

模板代码：

// 统计矩阵的行和与列和vector<int>horizontal(n,0);// 每行的和vector<int>vertical(m,0);// 每列的和// 统计行和for(inti=0;i<n;i++){for(intj=0;j<m;j++){horizontal[i]+=matrix[i][j];}}// 统计列和for(intj=0;j<m;j++){for(inti=0;i<n;i++){vertical[j]+=matrix[i][j];}}

5. 数组操作的时间复杂度

注意：

• 数组的随机访问是O(1)
• 插入和删除操作需要移动元素，时间复杂度为O(n)
• 前缀和可以优化区间和查询到O(1)

6. 何时使用数组技巧

6.1 使用场景

1. 区间和问题

   • 多次查询数组的区间和
   • 使用前缀和优化查询效率

2. 矩阵遍历问题

   • 螺旋矩阵遍历
   • 矩阵的按行、按列遍历
   • 矩阵的统计操作

3. 数组基本操作

   • 数组的遍历
   • 数组元素的修改
   • 数组的查找

4. 二维数组问题

   • 矩阵的生成
   • 矩阵的旋转、转置
   • 矩阵的统计和计算

6.2 判断标准

当遇到以下情况时，考虑使用数组技巧：

• 需要多次查询区间和 → 使用前缀和
• 需要按特殊顺序遍历矩阵 → 使用螺旋矩阵技巧
• 需要统计矩阵的行和、列和 → 使用矩阵统计
• 需要快速访问元素 → 利用数组的随机访问特性

示例：

// 问题：多次查询数组的区间和// 暴力解法：每次查询O(n)for(inti=a;i<=b;i++){sum+=arr[i];}// 前缀和解法：预处理O(n)，查询O(1)vector<int>prefix(n);// 构造前缀和数组for(inti=0;i<n;i++){prefix[i]=(i==0?arr[i]:prefix[i-1]+arr[i]);}// 查询区间和intsum=prefix[b]-(a>0?prefix[a-1]:0);

7. 数组操作的优缺点

7.1 优点

• 随机访问：通过索引可以在O(1)时间内访问任意元素
• 内存连续：数组元素在内存中连续存储，访问效率高
• 实现简单：数组操作逻辑清晰，易于实现
• 前缀和优化：可以将区间和查询优化到O(1)

7.2 缺点

• 固定大小：数组大小在创建时确定（C++中vector是动态数组）
• 插入删除慢：插入和删除操作需要移动元素，时间复杂度为O(n)
• 空间限制：需要连续的内存空间
• 无法直接删除：数组元素不能直接删除，只能覆盖

8. 常见题型总结

8.1 前缀和类

1. 区间和查询

   • 使用前缀和数组快速计算区间和
   • 时间复杂度：预处理O(n)，查询O(1)

2. 子数组和问题

   • 结合前缀和和哈希表
   • 可以解决子数组和等于k的问题

8.2 矩阵类

1. 螺旋矩阵

   • 按螺旋顺序遍历或生成矩阵
   • 使用循环不变量（左闭右开）

2. 矩阵统计

   • 统计矩阵的行和、列和
   • 矩阵的旋转、转置

3. 矩阵遍历

   • 按行遍历、按列遍历
   • 对角线遍历等特殊遍历方式

8.3 数组基本操作类

1. 数组遍历

   • 一维数组遍历
   • 二维数组遍历

2. 数组修改

   • 元素的覆盖
   • 元素的移动

9. 总结

普通数组是基础的数据结构，掌握数组的基本操作和常用技巧对于解决算法问题至关重要。

核心要点：

1. 数组特性：连续内存、随机访问、元素覆盖
2. 前缀和：用于优化区间和查询，预处理O(n)，查询O(1)
3. 矩阵操作：螺旋矩阵、矩阵统计、矩阵遍历
4. 时间复杂度：访问O(1)，遍历O(n)，插入删除O(n)
5. 空间复杂度：通常为O(1)或O(n)

使用建议：

• 区间和问题优先考虑前缀和
• 矩阵遍历问题考虑螺旋矩阵技巧
• 注意数组的边界条件
• 利用数组的随机访问特性
• 合理使用循环不变量

常见题型总结：

• 前缀和类：区间和查询、子数组和问题
• 矩阵类：螺旋矩阵、矩阵统计、矩阵遍历
• 数组基本操作：数组遍历、数组修改