数组

大家好，我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分：

  1. 理论介绍

  2. 源码分析

  3. 数据结构实现？

  4. 题目练习（按照算法思想分类）

  5. 梳理对应的 sdk 包

  6. 应用实战

因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。

简单介绍1，重点为4。其他不是本系列的重点。

chat

介绍一下数组

下面是对数组（Array）这个数据结构介绍，包括它的基本概念、特点、常见操作、时间复杂度分析、优缺点、以及在实际中的应用。

一、什么是数组（Array）？

数组（Array） 是一种线性数据结构，用于存储固定大小的同类型元素集合。这些元素在内存中是连续存储的，可以通过**索引（index）**直接访问。

比如一个整数数组：[10, 20, 30, 40]，其中第一个元素 10 的索引是 0，第二个是 1，以此类推。

二、数组的特点

特性 说明
顺序存储 数组的元素在内存中是连续存放的
随机访问 可以通过下标 O(1) 时间快速访问任意元素
类型一致 数组中的所有元素类型必须相同（在强类型语言中）
长度固定 大多数语言中，定义后大小不能改变（如 Java、C/C++ 中的普通数组）

三、常见操作及复杂度

操作 说明 时间复杂度
访问元素 通过下标访问 arr[i] O(1)
更新元素 修改某个位置的值 O(1)
插入元素 在中间插入一个新值（要移动元素） O(n)
删除元素 删除中间某个值（要移动元素） O(n)
遍历数组 用循环访问每个元素 O(n)
查找元素 线性查找（无序数组） O(n)
二分查找 在有序数组中查找 O(log n)

四、数组的优缺点

✅ 优点

  • 访问效率高：通过索引快速读取或修改元素，时间复杂度为 O(1)。
  • 结构简单：实现容易，适合用作其他数据结构的底层基础（如堆、栈、队列等）。
  • 空间紧凑：连续内存分配，节省空间。

❌ 缺点

  • 插入/删除效率低：非尾部插入或删除需要移动大量元素。
  • 容量固定：定义时必须指定大小，不易动态扩容（除非使用动态数组，如 ArrayList）。
  • 内存要求高：连续内存块在大数组下可能导致内存

密切相关的算法

✅ 数组密切关联的核心算法整理

🟢 一、查找类算法（适用于有序/无序数组）

  • 二分查找（Binary Search）

    • 要求数组有序，时间复杂度 O(log n)
    • 应用：查找目标值、左边界、右边界（lower_bound/upper_bound）
    • ✨ LeetCode 模板题：704、35、34

  • 哈希查找（Hash + Map）

    • 用于无序数组中快速定位目标值或频次统计
    • 应用：两数之和、前缀频率统计、元素是否重复

🔵 二、指针/窗口类算法（适合线性遍历、局部范围处理）

  • 双指针（Two Pointers）

    • 用于处理有序数组、区间问题、去重等
    • 典型场景：快慢指针、对撞指针
    • ✨ 例题：26（原地去重）、167（两数之和 II）、283（移动零）

  • 滑动窗口（Sliding Window）

    • 动态维护一个区间，用于求解最大/最小子数组、满足条件的子数组
    • 分为：固定窗口 & 可变窗口
    • ✨ 例题：209（最小子数组）、3（无重复字符的最长子串）

🟡 三、前缀思想类算法

  • 前缀和（Prefix Sum）

    • 快速计算任意子数组的和，时间从 O(n) 降到 O(1)
    • 应用：子数组和固定值、二维区域和
    • ✨ 例题：560（和为 K 的子数组）、303（区域和检索）

  • 差分数组（Difference Array）

    • 主要用于区间更新优化，减少重复计算
    • ✨ 应用题：370（区间加法）

🟠 四、排序类算法（很多题的前置步骤）

  • 冒泡/插入/选择排序

    • 入门级算法，理解排序原理和交换机制

  • 快速排序、归并排序

    • 快速排序：分治法的代表，平均 O(n log n)
    • 归并排序：适合求逆序对等场景
    • ✨ 例题：912（排序数组）、315（计算右侧小于当前元素的个数）

  • 排序后处理类问题

    • 如：三数之和（排序后双指针）、合并区间、最大间距

🔴 五、构造类 / 模拟类算法

  • 数组旋转（翻转法、环状替换）

    • ✨ 例题：189（旋转数组）

  • 原地修改 / 原地删除元素

    • 应用场景广泛，涉及数组压缩、空间优化
    • ✨ 例题：27（移除元素）、80（删除有序数组中重复项 II）

  • 矩阵处理（二维数组的进阶）

    • 旋转矩阵、螺旋遍历、压缩行列等
    • ✨ 例题：48（旋转图像）、73（矩阵置零）

🟣 六、组合与变形类算法

  • 子集 / 子数组 / 子序列 枚举

    • 回溯、位运算、滑动窗口等
    • ✨ 例题：78（子集）、90（子集 II）

  • 贪心算法 + 数组

    • 特别适合调度问题、区间覆盖、跳跃游戏
    • ✨ 例题：55（能否跳到最后）、45（最小跳跃次数）

  • 堆栈模拟数组操作（单调栈/单调队列）

    • 用于求区间最大最小值、下一个更大元素
    • ✨ 例题：739（每日温度）、84（柱状图最大矩形）

从 leetcode 推荐最值得练习的 10 道数组题

LeetCode 上有许多经典的数组问题，它们涉及不同的技术点和技巧，以下是我推荐的最值得练习的 10 道数组题（按难度从易到难排序）：

1. Two Sum (1)

  • 题目链接: Two Sum
  • 难度: 简单
  • 重点: 基本的哈希表技巧，快速查找已遍历过的元素。

2. Best Time to Buy and Sell Stock (121)

3. Rotate Array (189)

  • 题目链接: Rotate Array
  • 难度: 中等
  • 重点: 数组旋转，可以通过反转三次数组来解决。

4. Move Zeroes (283)

  • 题目链接: Move Zeroes
  • 难度: 简单
  • 重点: 数组操作，双指针技巧。

5. Container With Most Water (11)

6. 3Sum (15)

  • 题目链接: 3Sum
  • 难度: 中等
  • 重点: 排序+双指针技巧，找到所有满足条件的三元组。

7. Subarray Sum Equals K (560)

  • 题目链接: Subarray Sum Equals K
  • 难度: 中等
  • 重点: 前缀和+哈希表，动态求解连续子数组和。

8. Maximum Subarray (53)

  • 题目链接: Maximum Subarray
  • 难度: 中等
  • 重点: 动态规划，寻找最大和子数组。

9. Product of Array Except Self (238)

10. Find Minimum in Rotated Sorted Array (153)

这些题目覆盖了数组操作的多种常见模式，掌握它们可以帮助你提高在数组处理上的能力，特别是对于面试中的数组问题。

拓展的一些技巧和类型

这是个很棒的问题！

在算法题中，数组相关的技巧 是很多题目的核心基础。你已经列出了很多重要的技巧：

  • ✅ 遍历
  • ✅ 滑动窗口
  • ✅ 双指针
  • ✅ 前缀和
  • ✅ 差分数组
  • ✅ 矩阵技巧（如二维前缀和、螺旋、DFS/BFS 等）

除了这些，还有不少和数组关系非常密切的算法/技巧，我来分类整理一下，方便你系统掌握。

🧠 一、数据预处理类技巧（和前缀和/差分类似）

技巧 说明 常见题目
✅ 前缀积 / 前缀最大/最小 pre[i] = pre[i-1] * nums[i]，常用于快速计算积或范围最值 LeetCode 238
✅ 后缀数组 从右往左构建，与前缀数组搭配使用 LeetCode 238、42
✅ 计数数组（桶） 频率统计、哈希表的替代品 LeetCode 347、164
✅ 差分前缀和结合 比如差分解决多次区间修改，前缀和还原 LeetCode 1109、1094

⚡ 二、查找类技巧（离散化、二分、哈希）

技巧 说明 适用场景
✅ 离散化 把大范围数字映射到小范围 树状数组 / 线段树 等数据结构配合
✅ 二分查找 / 二分答案 O(logn) 查找目标元素 / 判断某个条件是否可行 LeetCode 34、875、1283
✅ 哈希表 统计频率/判断存在性，处理重复值 TwoSum、SubarraySum 等
✅ 坐标哈希 用于处理稀疏数组、稀疏矩阵 LeetCode 2536、1034

🧊 三、空间压缩/动态技巧

技巧 说明 例子
✅ 状态压缩 使用位运算表示数组/集合的状态 LeetCode 698、691
✅ 差分 + 前缀和优化空间 将二维更新压成一维 LeetCode 370
✅ 滚动数组（滚动DP） 节省空间的动态规划技巧 LeetCode 70、62
✅ 双端队列优化窗口 滑动窗口最值 / 单调队列 LeetCode 239、862

💥 四、排序类 + 归并 + 树状结构

技巧 说明 应用
✅ 排序 + 枚举/分类 常与贪心/双指针结合 LeetCode 56、435
✅ 归并排序求逆序对 利用 merge 步计算逆序对个数 LeetCode 315
✅ 树状数组 支持前缀和查询 + 单点修改 LeetCode 307、315
✅ 线段树 支持区间修改/查询 LeetCode 307、699
✅ 并查集（按秩+路径压缩） 用于连通块判断，常见在图+数组混合题 LeetCode 547、1319

🌈 五、子数组/子序列类技巧

技巧 说明 常用套路
✅ 枚举子数组/子序列 暴力 + 优化（滑窗、前缀和、哈希等） LeetCode 560、523
✅ 中心扩展 常用于最长回文子串 LeetCode 5
✅ 动态规划 子序列/子数组的结构性递推 LeetCode 300、53、198
✅ 单调栈 查找下一个更大/更小元素 LeetCode 84、739、496

📐 六、矩阵和二维数组技巧（和数组密切相关）

技巧 说明 应用
✅ 二维前缀和 预处理二维区域和 LeetCode 304、1314
✅ 二维差分 多次修改 + 一次还原 LeetCode 2536
✅ DFS/BFS 遍历 图 + 矩阵的基础 LeetCode 200、695
✅ 螺旋遍历 处理旋转、走位问题 LeetCode 54、59
✅ 滑动窗口最大值 二维滑动窗口优化 LeetCode 239（扩展）

🧩 七、其他零散但实用技巧

技巧 说明 应用题目
✅ 贪心与数组结合 常结合排序、遍历处理区间/覆盖问题 LeetCode 452、435
✅ 快速幂/前缀积 数组积相关处理 LeetCode 238、1481
✅ 模拟题技巧 比如模拟消除、旋转、重排等 LeetCode 73、289
✅ 滚动哈希 快速查找重复子串 LeetCode 1044、187

🔚 总结表格

分类 代表技巧
遍历类 遍历、双指针、滑窗
前缀/差分类 前缀和、差分、后缀数组
查找类 二分、哈希、离散化
空间/状态优化 状压、滚动数组、差分压缩
排序/归并类 排序、归并逆序对、树状数组、线段树
子数组/序列 动规、中心扩展、单调栈
矩阵类 二维差分、DFS/BFS、旋转模拟
特殊技巧 快速幂、滚动哈希、模拟题技巧

如果你是为了刷题而整理这类知识，我可以帮你做一张「数组技巧知识图谱 + 题目索引表」，要不要试试？