跳到主要内容

数组

线性数据结构 | JavaGuide

知识点概述​

数组是最基本的数据结构之一，由相同类型的元素（element）组成，并且是使用一块连续的内存来存储。可以利用元素的索引（index）计算出该元素对应的存储地址。

核心特性​

  • 随机访问：O(1) 时间复杂度通过索引访问元素
  • 连续存储：元素在内存中连续排列
  • 固定类型：所有元素类型相同
  • 固定大小：大多数语言中数组大小固定（动态数组除外）

时间复杂度​

操作时间复杂度说明
访问O(1)通过索引直接计算地址
搜索O(n)需要遍历数组
插入（末尾）O(1)动态数组末尾插入均摊 O(1)
插入（中间）O(n)需要移动后续元素，最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除（末尾）O(1)直接移除末尾元素
删除（中间）O(n)需要移动后续元素，最坏的情况发生在删除数组的开头并需要移动第一元素后面所有的元素时

数组 vs 链表：

  • 数组支持随机访问，链表不支持
  • 数组使用连续内存空间对 CPU 的缓存机制友好，链表则相反
  • 数组的大小固定，链表则天然支持动态扩容。如果声明的数组过小，需要另外申请一个更大的内存空间存放数组元素，然后将原数组拷贝进去，这个操作是比较耗时的！

常见题型​

1. 双指针​

  • 两数之和类问题
  • 数组去重
  • 移动零

相关题目：

2. 滑动窗口​

  • 子数组问题
  • 最大/最小子数组

3. 前缀和​

  • 区间和查询
  • 连续子数组和

4. 二分查找​

  • 搜索元素
  • 搜索插入位置

解题技巧​

技巧 1：双指针优化​

在有序数组或需要双向遍历时，使用双指针可以降低时间复杂度。

# 示例：双指针模板
left, right = 0, len(arr) - 1
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

技巧 2：原地修改​

当空间复杂度要求 O(1) 时，考虑原地修改数组。

技巧 3：哈希表辅助​

用哈希表记录已访问的元素，实现 O(1) 查找。

相关知识点​

题目列表​

按难度分类：

简单：

中等：

  • TBD

困难：

学习资源​

  • 《算法导论》第 2 章
  • LeetCode 数组专题
加载评论中...