一、先想明白：为什么要有数组？

如果没有数组，你想存一个班 50 个学生的数学成绩，你需要写：

score1=85
score2=92
score3=78
...
score50=66

这显然是灾难。数组的诞生，就是为了解决「批量存储和访问同类型数据」的问题。

它用一个统一的名字（数组名）代表这一组数据，用 ** 下标（索引）** 来区分每个元素，这样你就可以用scores[0]、scores[1]...scores[49]来访问任意一个学生的成绩。

---

二、数组的本质：连续的内存空间

✅ 核心思想（刻在脑子里）

用一块连续的、固定大小的内存空间，换取 O (1) 的随机访问能力。

这是数组所有特性的根源，也是它和其他所有数据结构最本质的区别。

生活化类比

数组就像一排连续的酒店房间：

• 酒店名字 = 数组名
• 房间号 = 数组下标（从 0 开始，不是 1！）
• 每个房间只能住同类型的客人（比如都是单人房）= 数组元素类型相同
• 房间是连续的，知道第一个房间的门牌号，就能直接算出第 N 个房间的门牌号 = 数组的随机访问

关键特性

1. 内存连续：这是最重要的特性，没有之一
2. 大小固定：创建时必须指定大小，之后不能改变
3. 元素同类型：所有元素占用的内存大小相同

---

三、数组的基本操作与复杂度

所有复杂度都可以从「连续内存」这个本质推导出来，不需要死记硬背。

表格

操作	时间复杂度	为什么？（从本质推导）
随机访问（查指定下标）	O(1)	直接用公式计算地址：元素地址 = 数组首地址 + 下标 × 单个元素大小
尾部插入 / 删除	O(1)	不需要移动其他元素
中间 / 头部插入 / 删除	O(n)	插入 / 删除位置后面的所有元素，都必须整体往后 / 往前挪一个位置，腾出空间
查找（不知道下标）	O(n)	只能从头开始一个一个找

举个例子

假设数组[1,2,3,4,5]存在内存中，首地址是 100，每个 int 占 4 个字节：

• 第 0 个元素地址：100 + 0×4 = 100
• 第 2 个元素地址：100 + 2×4 = 108
• 现在要在第 2 个位置插入元素 6，那么原来的 3、4、5 都要往后挪一个位置，一共移动 3 个元素，所以时间复杂度是 O (n)

---

四、数组的核心解题思想：双指针法

数组 90% 的面试题，都可以用双指针法解决。这是线性结构（数组、链表、字符串）通用的核心思想，必须彻底掌握。

双指针法的本质：用两个指针在数组上移动，把两层循环的 O (n²) 时间复杂度，优化成一层循环的 O (n)。

类型 1：快慢指针（原地修改数组）

适用场景

所有要求 **「原地修改数组」** 的题目（不能使用额外的数组空间）。

核心思想

• 慢指针：指向最终结果数组中，下一个应该存放元素的位置
• 快指针：遍历原数组，寻找符合条件的元素
• 当快指针找到符合条件的元素时，就把它赋值给慢指针指向的位置，然后慢指针向前走一步

---

例题 1：LeetCode 283. 移动零

题目：给定一个数组nums，将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。必须在原数组上操作，不能拷贝额外的数组。

错误思路（暴力法）：遍历数组，遇到 0 就把它和后面的元素交换，时间复杂度 O (n²)

正确思路（快慢指针）：

1. 慢指针slow初始化为 0，指向结果数组第一个应该放元素的位置
2. 快指针fast遍历整个数组
3. 当fast遇到非零元素时，把nums[fast]赋值给nums[slow]，然后slow += 1
4. 遍历结束后，slow之前的所有元素都是非零的，把slow之后的所有元素都设为 0

逐行解析代码

python

运行

def moveZeroes(nums):
    """
    :type nums: List[int]
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

# 测试代码
if __name__ == "__main__":
    # 测试用例1
    nums1 = [0, 1, 0, 3, 12]
    print("原始数组:", nums1)
    moveZeroes(nums1)
    print("移动零后:", nums1)
    
    # 测试用例2
    nums2 = [0]
    print("\n原始数组:", nums2)
    moveZeroes(nums2)
    print("移动零后:", nums2)
    
    # 测试用例3
    nums3 = [1, 2, 3, 4, 5]
    print("\n原始数组:", nums3)
    moveZeroes(nums3)
    print("移动零后:", nums3)
    
    # 测试用例4
    nums4 = [0, 0, 0, 1, 2, 3]
    print("\n原始数组:", nums4)
    moveZeroes(nums4)
    print("移动零后:", nums4)
    
    # 测试用例5
    nums5 = [1, 0, 0, 2, 0, 3, 0, 4, 0]
    print("\n原始数组:", nums5)
    moveZeroes(nums5)
    print("移动零后:", nums5)

时间复杂度：O (n)，只遍历了数组两次空间复杂度：O (1)，没有使用额外空间

---

举一反三：LeetCode 27. 移除元素

题目：给你一个数组nums和一个值val，原地移除所有数值等于val的元素，并返回移除后数组的新长度。

你会发现，这道题和移动零思路完全一样，只是第二步不需要了：

python

运行

def removeElement(nums, val):
    """
    :type nums: List[int]
    :type val: int
    :rtype: int
    """
    # 慢指针，指向下一个不等于val的元素应该放置的位置
    slow = 0
    
    # 快指针遍历数组
    for fast in range(len(nums)):
        # 如果当前元素不等于目标值
        if nums[fast] != val:
            # 将元素移到前面
            nums[slow] = nums[fast]
            slow += 1
    
    return slow

# 测试代码
if __name__ == "__main__":
    # 测试用例1
    nums1 = [3, 2, 2, 3]
    val1 = 3
    print(f"原始数组: {nums1}, 要移除的值: {val1}")
    new_length = removeElement(nums1, val1)
    print(f"新长度: {new_length}")
    print(f"前{new_length}个元素: {nums1[:new_length]}")
    
    # 测试用例2
    nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
    val2 = 2
    print(f"\n原始数组: {nums2}, 要移除的值: {val2}")
    new_length = removeElement(nums2, val2)
    print(f"新长度: {new_length}")
    print(f"前{new_length}个元素: {nums2[:new_length]}")
    
    # 测试用例3
    nums3 = [1, 2, 3, 4, 5]
    val3 = 6
    print(f"\n原始数组: {nums3}, 要移除的值: {val3}")
    new_length = removeElement(nums3, val3)
    print(f"新长度: {new_length}")
    print(f"前{new_length}个元素: {nums3[:new_length]}")
    
    # 测试用例4
    nums4 = [1, 1, 1, 1, 1]
    val4 = 1
    print(f"\n原始数组: {nums4}, 要移除的值: {val4}")
    new_length = removeElement(nums4, val4)
    print(f"新长度: {new_length}")
    print(f"前{new_length}个元素: {nums4[:new_length]}")
    
    # 测试用例5
    nums5 = []
    val5 = 0
    print(f"\n原始数组: {nums5}, 要移除的值: {val5}")
    new_length = removeElement(nums5, val5)
    print(f"新长度: {new_length}")
    print(f"前{new_length}个元素: {nums5[:new_length] if new_length > 0 else '[]'}")

✅ 记住：所有「原地移除数组中特定元素」的题目，都是这个模板。

---

类型 2：左右指针（有序数组）

适用场景

数组是有序的（这是前提！）。

核心思想

• 左指针：指向数组的开头（最左边）
• 右指针：指向数组的结尾（最右边）
• 根据两个指针指向元素的和，判断应该移动哪个指针

---

例题 2：LeetCode 704. 二分查找

题目：给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回 - 1。

为什么二分查找必须用数组？因为二分查找需要随机访问中间元素，只有数组能做到 O (1) 的随机访问，链表做不到。

核心思路：

1. 左指针left初始化为 0，右指针right初始化为len(nums)-1
2. 计算中间位置mid = (left + right) // 2
3. 如果nums[mid] == target，找到目标，返回mid
4. 如果nums[mid] < target，说明目标在右半部分，left = mid + 1
5. 如果nums[mid] > target，说明目标在左半部分，right = mid - 1
6. 循环结束还没找到，返回 - 1

逐行解析代码

python

运行

def search(nums, target):
    left = 0
    right = len(nums) - 1  # 注意：右指针指向最后一个元素
    while left <= right:  # 注意：循环条件是<=，不是<
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

间复杂度：O (logn)，每次搜索范围缩小一半空间复杂度：O(1)

✅ 记住：只要题目说「数组有序」，第一反应就是二分查找。

---

五、数组的典型应用场景

1. 存储同类型的一组数据（比如学生成绩、商品列表）
2. 实现其他数据结构的底层（栈、队列、哈希表、堆、字符串）
3. 所有需要随机访问的场景
4. 数据量大小已知，且查多改少的场景