跳转至

02-数组（Array）详解

重要性：⭐⭐⭐⭐⭐ 难度：⭐ 学习时间：2-3天 前置知识：无

📚 目录

  1. 什么是数组
  2. 数组的内存结构
  3. 数组的操作详解
  4. Python中的数组
  5. C++中的数组
  6. 经典面试题
  7. 实战应用
  8. 练习题

什么是数组？

基本概念

数组是最基础的数据结构，用于存储相同类型的元素序列。

生活中的例子

想象一排储物柜：

Text Only
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
 0   1   2   3   4

  • 每个柜子（格子）存放一个物品
  • 每个柜子都有一个编号（索引）
  • 所有柜子连成一排，位置固定

为什么学数组？

✅ 优点： 1. 快速访问：通过索引直接访问，O(1)时间 2. 内存紧凑：元素连续存储，节省空间 3. 缓存友好：连续内存提高CPU缓存命中率

❌ 缺点： 1. 大小固定：创建后不能改变大小（大多数语言） 2. 插入删除慢：需要移动其他元素

数组的内存结构

内存可视化

Text Only
内存地址:  1000    1004    1008    1012    1016
           ┌────┐  ┌────┐  ┌────┐  ┌────┐  ┌────┐
数组内容:  │ 10 │  │ 20 │  │ 30 │  │ 40 │  │ 50 │
           └────┘  └────┘  └────┘  └────┘  └────┘
索引:        0       1       2       3       4

假设int占4字节，每个元素间隔4个字节

数组内存布局

图：数组在内存中的连续存储结构

关键特性

  1. 连续内存：数组元素在内存中是连续存放的
  2. 相同大小：每个元素占用相同的内存空间
  3. 随机访问：可以通过索引直接访问任意元素

为什么能O(1)访问？

Text Only
公式：元素地址 = 起始地址 + (索引 × 元素大小)

示例：
起始地址 = 1000
索引 = 3
元素大小 = 4字节（int）

访问arr[3]：
地址 = 1000 + (3 × 4) = 1012 ✅ 直接计算，无需遍历！

数组的操作详解

操作1：访问元素 (O(1))

Python
# 直接通过索引访问
arr = [10, 20, 30, 40, 50]

# 访问第3个元素（索引2）
element = arr[2]  # 30

# 访问第一个元素
first = arr[0]    # 10

# 访问最后一个元素
last = arr[-1]    # 50（Python特有）

时间复杂度：O(1) 原理：通过公式直接计算地址

操作2：修改元素 (O(1))

Python
arr = [10, 20, 30, 40, 50]

# 修改索引2的元素
arr[2] = 100
# 结果：[10, 20, 100, 40, 50]

# 复杂度：O(1) - 直接定位到位置并修改

操作3：在末尾添加 (均摊O(1))

Python
arr = [10, 20, 30]

# 添加到末尾
arr.append(40)
# 结果：[10, 20, 30, 40]

# 原理：
# 1. 如果有剩余空间，直接放入 → O(1)
# 2. 如果空间不足，扩容后放入 → O(n)
# 平均下来：均摊O(1)

扩容过程（Python list）：

Text Only
初始容量：4
[10, 20, 30, _]  添加40 → [10, 20, 30, 40]  ✓

添加50 → 空间不足，扩容！
旧数组：[10, 20, 30, 40]
新数组：[10, 20, 30, 40, _, _, _, _]  容量翻倍

复制所有元素 → [10, 20, 30, 40, 50, _, _, _]

操作4：在开头/中间插入 (O(n)) ⚠️

Python
arr = [10, 20, 30, 40, 50]

# 在索引1处插入25
arr.insert(1, 25)

# 过程：
# 步骤1：[10, 20, 30, 40, 50, _]  扩容
# 步骤2：[10, __, 20, 30, 40, 50]  从后往前移动
# 步骤3：[10, 25, 20, 30, 40, 50]  插入

# 结果：[10, 25, 20, 30, 40, 50]

# 为什么是O(n)？因为要移动n个元素！

插入过程详解：

Text Only
初始: [10, 20, 30, 40, 50]
索引:   0   1   2   3   4

在索引1插入25：

第1步：从后往前，每个元素向后移一位
       50 → 索引5
       40 → 索引4
       30 → 索引3
       20 → 索引2
       10 → 索引0（不动）

第2步：在索引1处放入25
       [10, 25, 20, 30, 40, 50]

移动了4个元素 → O(n)

数组插入操作

图：在索引1处插入25的过程演示

操作5：删除元素 (O(n)) ⚠️

Python
arr = [10, 20, 30, 40, 50]

# 删除索引2的元素
del arr[2]

# 过程：
# 初始: [10, 20, 30, 40, 50]
# 删除30: [10, 20, __, 40, 50]
# 前移:   [10, 20, 40, 50]  40和50向前移动

# 结果：[10, 20, 40, 50]

# 为什么是O(n)？因为要移动n个元素！

删除过程详解：

Text Only
初始: [10, 20, 30, 40, 50]
索引:   0   1   2   3   4

删除索引2的元素（30）：

第1步：删除30
       [10, 20, __, 40, 50]

第2步：从前往后，每个元素向前移一位
       40 → 索引2
       50 → 索引3

第3步：数组缩小
       [10, 20, 40, 50]

移动了2个元素 → O(n)

操作6：查找元素 (O(n))

Python
arr = [10, 20, 30, 40, 50]

# 线性查找30
for i in range(len(arr)):
    if arr[i] == 30:
        print(f"找到30，索引为{i}")
        break

# 为什么是O(n)？最坏情况要遍历整个数组！

查找过程详解：

Text Only
目标：查找30

数组：[10, 20, 30, 40, 50]

第1次比较：arr[0] = 10 ≠ 30
第2次比较：arr[1] = 20 ≠ 30
第3次比较：arr[2] = 30 = 30 ✓ 找到了！

最坏情况：查找50或不存在的元素
需要比较n次 → O(n)

操作7：遍历数组 (O(n))

Python
arr = [10, 20, 30, 40, 50]

# 方法1：for循环
for i in range(len(arr)):
    print(arr[i])

# 方法2：for-each循环
for element in arr:
    print(element)

# 方法3：enumerate（获取索引和值）
for index, value in enumerate(arr):
    print(f"索引{index}: {value}")

Python中的数组

Python List详解

Python
# 创建数组
arr = [1, 2, 3, 4, 5]

# 基本操作
print(len(arr))           # 长度: 5
print(arr[0])             # 访问: 1
print(arr[-1])            # 最后一个: 5
print(arr[1:4])           # 切片: [2, 3, 4]
print(arr[::2])           # 步长: [1, 3, 5]
print(arr[::-1])          # 反转: [5, 4, 3, 2, 1]

# 添加元素
arr.append(6)             # 末尾添加: [1, 2, 3, 4, 5, 6]
arr.insert(0, 0)          # 开头插入: [0, 1, 2, 3, 4, 5, 6]
arr.extend([7, 8])        # 扩展列表: [0, 1, 2, 3, 4, 5, 6, 7, 8]

# 删除元素
arr.pop()                 # 删除末尾: 返回8
arr.pop(0)                # 删除索引0: 返回0
arr.remove(3)             # 删除值3
del arr[1]                # 删除索引1

# 查找
print(3 in arr)           # 判断是否存在: True
print(arr.index(3))       # 查找索引: 2
print(arr.count(3))       # 计数: 1

# 排序
arr.sort()                # 原地排序
arr.sort(reverse=True)    # 降序排序
sorted_arr = sorted(arr)  # 返回新列表

# 其他操作
arr.reverse()             # 反转
arr.clear()               # 清空
arr.copy()                # 复制

Python数组的高级操作

Python
import numpy as np

# NumPy数组（更高效的数值计算）
np_arr = np.array([1, 2, 3, 4, 5])

# 向量化操作
np_arr * 2                # [2, 4, 6, 8, 10]
np_arr + 10               # [11, 12, 13, 14, 15]
np_arr > 3                # [False, False, False, True, True]

# 统计操作
np.mean(np_arr)           # 平均值: 3.0
np.sum(np_arr)            # 求和: 15
np.max(np_arr)            # 最大值: 5
np.min(np_arr)            # 最小值: 1

# 多维数组
matrix = np.array([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
])
print(matrix[0, 0])       # 1
print(matrix[:, 0])       # 第0列: [1, 4, 7]
print(matrix[0, :])       # 第0行: [1, 2, 3]

C++中的数组

C++原生数组

C++
#include <iostream>
using namespace std;

int main() {
    // 创建数组
    int arr[5] = {1, 2, 3, 4, 5};

    // 访问元素
    cout << arr[0] << endl;  // 1
    cout << arr[4] << endl;  // 5

    // 遍历数组
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // 获取数组大小
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "数组大小: " << size << endl;

    // 修改元素
    arr[2] = 100;

    // 数组越界（危险！）
    // arr[10] = 100;  // 未定义行为

    return 0;
}

C++ vector（动态数组）

C++
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 创建vector
    vector<int> arr = {1, 2, 3, 4, 5};

    // 基本操作
    cout << arr.size() << endl;        // 大小: 5
    cout << arr[0] << endl;            // 访问: 1
    cout << arr.front() << endl;       // 第一个: 1
    cout << arr.back() << endl;        // 最后一个: 5

    // 添加元素
    arr.push_back(6);                  // 末尾添加
    arr.insert(arr.begin(), 0);        // 开头插入

    // 删除元素
    arr.pop_back();                    // 删除末尾
    arr.erase(arr.begin() + 2);        // 删除索引2
    arr.clear();                       // 清空

    // 遍历
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // for-each循环
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;

    // 排序
    sort(arr.begin(), arr.end());              // 升序
    sort(arr.begin(), arr.end(), greater<int>()); // 降序

    // 查找
    auto it = find(arr.begin(), arr.end(), 3);
    if (it != arr.end()) {
        cout << "找到3" << endl;
    }

    // 二分查找（需要先排序）
    bool found = binary_search(arr.begin(), arr.end(), 3);

    return 0;
}

C++ array（固定大小数组）

C++
#include <iostream>  // 引入头文件
#include <array>
using namespace std;

int main() {
    // 创建array（C++11）
    array<int, 5> arr = {1, 2, 3, 4, 5};

    // 基本操作
    cout << arr.size() << endl;         // 5
    cout << arr[0] << endl;             // 1
    cout << arr.at(2) << endl;          // 3（带边界检查）

    // 遍历
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;

    // 填充
    arr.fill(0);  // 所有元素设为0

    return 0;
}

经典面试题

题目1：两数之和

问题描述： 给定一个整数数组 nums 和一个目标值 target，在数组中找出和为目标值的两个整数，返回它们的索引。

示例：

Text Only
输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：nums[0] + nums[1] = 2 + 7 = 9

解法1：暴力法（O(n²)）

Python
def two_sum_brute(nums, target):
    """
    暴力解法
    时间：O(n²)
    空间：O(1)
    """
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# 测试
print(two_sum_brute([2, 7, 11, 15], 9))  # [0, 1]

解法2：哈希表（O(n)）

Python
def two_sum_hash(nums, target):
    """
    哈希表解法
    时间：O(n)
    空间：O(n)
    """
    # 存储值到索引的映射
    hash_map = {}

    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i

    return []

# 测试
print(two_sum_hash([2, 7, 11, 15], 9))  # [0, 1]

# 过程详解：
# i=0, num=2, complement=7, hash_map={}, 7不在hash_map中
#         hash_map = {2: 0}
# i=1, num=7, complement=2, hash_map={2: 0}, 2在hash_map中！
#         返回 [hash_map[2], 1] = [0, 1] ✓

题目2：买卖股票的最佳时机

问题描述： 给定一个数组 prices，prices[i] 是某只股票在第i天的价格。设计算法计算最大利润。

示例：

Text Only
输入：[7, 1, 5, 3, 6, 4]
输出：5
解释：在第2天（价格=1）买入，第5天（价格=6）卖出，利润 = 6 - 1 = 5

解法：一次遍历（O(n)）

Python
def max_profit(prices):
    """
    时间：O(n)
    空间：O(1)
    """
    if not prices:
        return 0

    min_price = prices[0]  # 记录最低价格
    max_profit = 0         # 记录最大利润

    for price in prices:
        # 更新最低价格
        min_price = min(min_price, price)
        # 更新最大利润
        max_profit = max(max_profit, price - min_price)

    return max_profit

# 测试
print(max_profit([7, 1, 5, 3, 6, 4]))  # 5

# 过程详解：
# price=7: min_price=7, profit=0, max_profit=0
# price=1: min_price=1, profit=0, max_profit=0
# price=5: min_price=1, profit=4, max_profit=4
# price=3: min_price=1, profit=2, max_profit=4
# price=6: min_price=1, profit=5, max_profit=5 ✓
# price=4: min_price=1, profit=3, max_profit=5

图解：

Text Only
价格:  7
       │    6
       │    │     5
       │    │     │  4
       │    │     │  │  3
       │    │     │  │  │     1
       │    │     │  │  │     │
       └────┴─────┴──┴──┴─────┴
       0    1     2  3  4     5

最优：在1买入，在6卖出
利润 = 6 - 1 = 5

题目3：最大子数组和

问题描述： 给定一个整数数组 nums，找到一个具有最大和的连续子数组，返回其最大和。

示例：

Text Only
输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6

解法：Kadane算法（O(n)）

Python
def max_subarray(nums):
    """
    Kadane算法
    时间：O(n)
    空间：O(1)

    核心思想：
    - current_sum: 以当前元素结尾的子数组和
    - max_sum: 全局最大子数组和
    """
    if not nums:
        return 0

    current_sum = nums[0]
    max_sum = nums[0]

    for num in nums[1:]:  # 切片操作：[start:end:step]提取子序列
        # 选择：扩展当前子数组 OR 重新开始
        current_sum = max(num, current_sum + num)
        # 更新全局最大值
        max_sum = max(max_sum, current_sum)

    return max_sum

# 测试
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6

# 过程详解：
# num=-2: current=-2, max=-2
# num=1:  current=max(1, -2+1)=1, max=max(-2,1)=1
# num=-3: current=max(-3, 1-3)=-2, max=max(1,-2)=1
# num=4:  current=max(4, -2+4)=4, max=max(1,4)=4
# num=-1: current=max(-1, 4-1)=3, max=max(4,3)=4
# num=2:  current=max(2, 3+2)=5, max=max(4,5)=5
# num=1:  current=max(1, 5+1)=6, max=max(5,6)=6 ✓
# num=-5: current=max(-5, 6-5)=1, max=max(6,1)=6
# num=4:  current=max(4, 1+4)=5, max=max(6,5)=6

图解：

Text Only
数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

索引:  0   1   2   3   4   5   6   7   8
       ───┬───┬───┬───┬───┬───┬───┬───┬───
          │
          ├─ 子数组[0:1]: -2
          ├─ 子数组[1:1]: 1
          ├─ 子数组[1:2]: -2
          │
          ├─ 子数组[3:3]: 4
          ├─ 子数组[3:4]: 3
          ├─ 子数组[3:5]: 5
          ├─ 子数组[3:6]: 6 ✓ 最大
          ├─ 子数组[3:7]: 1
          └─ 子数组[3:8]: 5

题目4：删除有序数组中的重复项

问题描述： 给定一个升序排列的数组 nums，原地删除重复元素，使每个元素只出现一次，返回新长度。

示例：

Text Only
输入：nums = [1, 1, 2]
输出：2，nums = [1, 2]

输入：nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
输出：5，nums = [0, 1, 2, 3, 4]

解法：双指针（O(n)）

Python
def remove_duplicates(nums):
    """
    双指针解法
    时间：O(n)
    空间：O(1)

    核心思想：
    - slow: 慢指针，指向不重复区域的末尾
    - fast: 快指针，遍历整个数组
    """
    if not nums:
        return 0

    slow = 0  # 慢指针

    for fast in range(1, len(nums)):  # 快指针从1开始
        if nums[fast] != nums[slow]:  # 发现不同元素
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

# 测试
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
length = remove_duplicates(nums)
print(f"新长度: {length}")
print(f"数组前{length}个: {nums[:length]}")
# 输出：新长度: 5
#      数组前5个: [0, 1, 2, 3, 4]

# 过程详解：
# 初始: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
#        ↑
#      slow=0

# fast=1: nums[1]=0 == nums[0]=0，跳过
# fast=2: nums[2]=1 != nums[0]=0
#         slow=1, nums[1]=1
#         [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
#            ↑     ↑
#          slow=1 fast=2

# fast=3: nums[3]=1 == nums[1]=1，跳过
# fast=4: nums[4]=1 == nums[1]=1，跳过
# fast=5: nums[5]=2 != nums[1]=1
#         slow=2, nums[2]=2
#         [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
#               ↑           ↑
#             slow=2     fast=5

# ...继续直到fast遍历完

题目5：轮转数组

问题描述： 给定一个数组 nums，将数组中的元素向右轮转 k 步。

示例：

Text Only
输入：nums = [1, 2, 3, 4, 5, 6, 7], k = 3
输出：[5, 6, 7, 1, 2, 3, 4]

解释：
- 向右轮转1步: [7, 1, 2, 3, 4, 5, 6]
- 向右轮转2步: [6, 7, 1, 2, 3, 4, 5]
- 向右轮转3步: [5, 6, 7, 1, 2, 3, 4]

解法1：使用额外数组（O(n)空间）

Python
def rotate_extra_array(nums, k):
    """
    额外数组解法
    时间：O(n)
    空间：O(n)
    """
    n = len(nums)
    k %= n  # 处理k >= n的情况

    # 创建新数组
    result = [0] * n

    # 将后k个元素放到前面
    for i in range(k):
        result[i] = nums[n - k + i]

    # 将前n-k个元素放到后面
    for i in range(n - k):
        result[k + i] = nums[i]

    # 复制回原数组
    for i in range(n):
        nums[i] = result[i]

# 测试
nums = [1, 2, 3, 4, 5, 6, 7]
rotate_extra_array(nums, 3)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

解法2：三次翻转（O(1)空间）

Python
def rotate_reverse(nums, k):
    """
    三次翻转解法（推荐！）
    时间：O(n)
    空间：O(1)

    核心思想：
    1. 翻转整个数组
    2. 翻转前k个元素
    3. 翻转后n-k个元素
    """
    n = len(nums)
    k %= n

    # 辅助函数：翻转数组的指定区间
    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    # 三次翻转
    reverse(0, n - 1)      # 翻转整个数组
    reverse(0, k - 1)      # 翻转前k个
    reverse(k, n - 1)      # 翻转后n-k个

# 测试
nums = [1, 2, 3, 4, 5, 6, 7]
rotate_reverse(nums, 3)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

# 过程详解：
# 初始: [1, 2, 3, 4, 5, 6, 7]
#
# 第1次翻转（整体）:
#       [7, 6, 5, 4, 3, 2, 1]
#
# 第2次翻转（前3个）:
#       [5, 6, 7, 4, 3, 2, 1]
#        ────┘
#
# 第3次翻转（后4个）:
#       [5, 6, 7, 1, 2, 3, 4]
#               └──────┘

图解三次翻转：

Text Only
原始: [1, 2, 3, 4, 5, 6, 7], k=3

第1步：整体翻转
┌───────────────────────┐
│  1   2   3   4   5   6   7  │
└───────────────────────┘
         ↓ 翻转
┌───────────────────────┐
│  7   6   5   4   3   2   1  │
└───────────────────────┘

第2步：翻转前3个
┌─────┐───────────────────┐
│  7   6   5  │  4   3   2   1  │
└─────┘───────────────────┘
         ↓ 翻转
┌─────┐───────────────────┐
│  5   6   7  │  4   3   2   1  │
└─────┘───────────────────┘

第3步：翻转后4个
┌─────┐┬──────────────────┐
│  5   6   7  ││ 4   3   2   1  │
└─────┘┴──────────────────┘
                ↓ 翻转
┌─────┐┬──────────────────┐
│  5   6   7  ││ 1   2   3   4  │
└─────┘┴──────────────────┘

最终: [5, 6, 7, 1, 2, 3, 4] ✓

三次翻转旋转

图：使用三次翻转法将数组向右旋转3步

实战应用

应用1：机器学习中的数据预处理

Python
import numpy as np

def normalize_data(features):
    """
    数据标准化：将特征缩放到[0, 1]范围
    """
    feature_array = np.array(features)

    # 计算最小值和最大值
    min_val = np.min(feature_array, axis=0)
    max_val = np.max(feature_array, axis=0)

    # 标准化公式：(x - min) / (max - min)
    normalized = (feature_array - min_val) / (max_val - min_val)

    return normalized

# 示例：标准化鸢尾花数据集
features = [
    [5.1, 3.5, 1.4, 0.2],  # 花萼长度、宽度，花瓣长度、宽度
    [4.9, 3.0, 1.4, 0.2],
    [7.0, 3.2, 4.7, 1.4],
    [6.3, 3.3, 6.0, 2.5]
]

normalized = normalize_data(features)
print("标准化后的数据:")
print(normalized)

应用2：滑动窗口技术

Python
def max_sliding_window(nums, k):
    """
    滑动窗口最大值
    给定数组nums和窗口大小k，返回每个窗口的最大值

    示例：
    输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
    输出：[3, 3, 5, 5, 6, 7]
    """
    from collections import deque

    result = []
    window = deque()  # 存储索引（非值！）

    for i, num in enumerate(nums):  # enumerate同时获取索引和值
        # 移除窗口外的元素
        while window and window[0] <= i - k:
            window.popleft()

        # 移除小于当前元素的值
        while window and nums[window[-1]] < num:  # 负索引：从末尾倒数访问元素
            window.pop()

        # 添加当前元素
        window.append(i)

        # 记录窗口最大值
        if i >= k - 1:
            result.append(nums[window[0]])

    return result

# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(f"滑动窗口最大值: {max_sliding_window(nums, k)}")
# 输出: [3, 3, 5, 5, 6, 7]

# 图解：
# nums = [1, 3, -1, -3, 5, 3, 6, 7]
#
# 窗口1: [1, 3, -1]   → 最大值: 3
# 窗口2: [3, -1, -3]  → 最大值: 3
# 窗口3: [-1, -3, 5]  → 最大值: 5
# 窗口4: [-3, 5, 3]   → 最大值: 5
# 窗口5: [5, 3, 6]    → 最大值: 6
# 窗口6: [3, 6, 7]    → 最大值: 7

滑动窗口可视化

图：滑动窗口在数组中移动并找出每个窗口的最大值

应用3：前缀和

Python
def prefix_sum(arr):
    """
    前缀和数组
    用于快速计算区间和
    """
    n = len(arr)
    prefix = [0] * (n + 1)

    # prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]

    return prefix

def range_sum(prefix, left, right):
    """
    计算区间[left, right]的和
    时间：O(1)
    """
    return prefix[right + 1] - prefix[left]

# 测试
arr = [1, 2, 3, 4, 5]
prefix = prefix_sum(arr)
print(f"前缀和数组: {prefix}")  # [0, 1, 3, 6, 10, 15]

# 快速计算区间和
print(f"区间[1, 3]的和: {range_sum(prefix, 1, 3)}")  # 2+3+4=9
print(f"区间[0, 4]的和: {range_sum(prefix, 0, 4)}")  # 1+2+3+4+5=15

# 图解：
# arr:     [1, 2, 3, 4, 5]
# 索引:     0  1  2  3  4
#
# prefix: [0, 1, 3, 6, 10, 15]
# 索引:    0  1  2  3   4   5
#
# prefix[i] = arr[0..i-1]的和
#
# 区间和公式：
# arr[left..right]的和 = prefix[right+1] - prefix[left]
#
# 示例：arr[1..3]的和
# = prefix[4] - prefix[1]
# = 10 - 1
# = 9 ✓ (即 2+3+4)

前缀和数组

图：前缀和数组及其快速计算区间和的原理

应用4：矩阵操作

Python
import numpy as np

def matrix_operations():
    """矩阵基本操作"""

    # 创建矩阵
    matrix = np.array([
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ])

    print("原始矩阵:")
    print(matrix)

    # 访问元素
    print(f"\n元素[0,0]: {matrix[0, 0]}")  # 1

    # 访问行
    print(f"第0行: {matrix[0, :]}")  # [1, 2, 3]

    # 访问列
    print(f"第0列: {matrix[:, 0]}")  # [1, 4, 7]

    # 矩阵转置
    print("\n转置矩阵:")
    print(matrix.T)

    # 矩阵加减
    matrix2 = np.array([
        [9, 8, 7],
        [6, 5, 4],
        [3, 2, 1]
    ])
    print("\n矩阵相加:")
    print(matrix + matrix2)

    # 矩阵乘法
    print("\n矩阵乘法:")
    print(np.dot(matrix, matrix2))

    # 逐元素操作
    print("\n每个元素乘以2:")
    print(matrix * 2)

    # 矩阵求和
    print(f"\n所有元素的和: {np.sum(matrix)}")
    print(f"每行的和: {np.sum(matrix, axis=1)}")
    print(f"每列的和: {np.sum(matrix, axis=0)}")

# 运行
matrix_operations()

练习题

基础题

  1. 找出数组中第二大的数

    Python
    def find_second_largest(arr):
    # 你的代码
    pass

  2. 反转数组（不使用额外空间）

    Python
    def reverse_array(arr):
    # 你的代码
    pass

  3. 检查数组是否有序

    Python
    def is_sorted(arr):
    # 你的代码
    pass

中等题

  1. 合并两个有序数组

    Python
    def merge_sorted_arrays(arr1, arr2):
    # 你的代码
    pass

  2. 移除所有等于val的元素

    Python
    def remove_element(nums, val):
    # 你的代码
    pass

  3. 找出数组中缺失的数

    Python
    # 给定包含n个不同数字的数组，范围为[0, n]
# 找出缺失的数字
def find_missing_number(nums):
    # 你的代码
    pass

困难题

  1. 盛水最多的容器

    Python
    def max_area(height):
    """
    给定n个非负整数，每个代表坐标( i, height[i] )
    找出两条线，使其与x轴构成的容器能容纳最多的水

    示例：
    输入：[1,8,6,2,5,4,8,3,7]
    输出：49
    """
    # 你的代码
    pass

  2. 除自身以外数组的乘积

    Python
    def product_except_self(nums):
    """
    给定长度为n的整数数组nums
    返回数组answer，其中answer[i]等于nums中除nums[i]外其余元素的乘积

    要求：O(n)时间，不使用除法
    """
    # 你的代码
    pass

📝 总结

关键要点

✅ 数组特点： - 连续内存存储 - 支持随机访问O(1) - 插入/删除O(n)

✅ 常用操作： - 访问/修改：O(1) - 添加/删除：O(n) - 查找：O(n)（二分搜索除外）

✅ Python vs C++： - Python list：动态数组，功能丰富 - C++ vector：高效，类型安全

✅ 经典技巧： - 双指针 - 滑动窗口 - 前缀和 - 哈希表配合

下一步

继续学习： - 链表 - 动态数据结构 - 栈和队列 - 受限操作的线性结构

📚 扩展阅读