数组与复杂度

数组的本质

数组是最基础、也是面试中出现频率最高的数据结构。理解数组，不只是会写 nums[i]，而是要清楚：元素在内存里是否连续、下标如何映射到地址、哪些操作是常数时间、哪些必须线性扫描。

在大多数语言中，数组（或动态数组如 Python 的 list、Go 的 slice 底层）提供 O(1) 随机访问：给定下标 i，CPU 通过「基址 + 偏移」直接读到值。这是哈希表、堆、排序等无数算法能够高效运行的前提。

连续内存还带来 缓存友好：遍历数组时，相邻元素往往落在同一缓存行，比链表指针跳转快一个数量级。面试里若要在「遍历 + 局部性」与「中间插入」之间权衡，数组几乎总是遍历场景的首选。

常见操作与复杂度

| 操作 | 无序数组 | 说明 | |------|----------|------| | 按下标访问 | O(1) | 核心优势 | | 末尾追加（均摊） | O(1) | 动态数组扩容均摊 | | 头部/中间插入 | O(n) | 元素搬移 | | 按值查找 | O(n) | 需线性扫描 | | 排序后二分 | O(log n) | 需先有序 |

原地修改（in-place）是数组题的高频考点：用交换、双指针、前缀和等方式，在不额外开 O(n) 空间的前提下完成反转、去重、移动零等操作。

def reverse_inplace(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

时间与空间复杂度

时间复杂度描述随输入规模 n 增长，操作次数的量级。常见阶：O(1)、O(log n)、O(n)、O(n log n)、O(n²)。分析时问三件事：循环嵌套几层？每层迭代多少次？递归深度是多少？

空间复杂度除辅助数组外，别忽略 递归调用栈。例如 naive 快排最坏 O(n) 栈深；归并排序 O(n) 辅助数组 + O(log n) 栈。

def max_subarray(nums):  # Kadane，O(n) 时间 O(1) 空间
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

面试实战要点

先问约束：n 多大？是否有序？能否改原数组？有无负数？

前缀和：区间和 O(1) 查询，配合哈希表做「和为 k 的子数组个数」。

差分数组：区间加法的 O(1) 单点更新技巧。

排序预处理：很多「两数之和变体」先排序再双指针。

本主题与后续 /zh/knowledge/master-plan/week01-two-pointers、week01-sliding-window 紧密衔接。建议配合站内算法 Lab 做 3～5 道数组基础题，形成「读题 → 判复杂度 → 选模板」的肌肉记忆。

本周自检

• 能口头解释 O(n) 与 O(n log n) 差一个 log 意味着什么（约 10⁶ 数据：10⁶ vs 2×10⁷ 量级）。
• 能手写反转、移动零、最大子数组和。
• 看到「子数组/子序列」立刻区分：子数组连续，子序列可跳。