Tech Interview Handbook 数组（Array）面试速查表：复杂度分析、七大经典技巧与高频题清单

本文基于 Tech Interview Handbook 仓库 中的官方学习文档 array.md 展开，系统讲解数组这一数据结构在编码面试中的核心考点：时间复杂度表、Subarray/Subsequence 等易混淆概念、滑窗/双指针等七大解题技巧、边界条件清单，以及必须练习与进阶练习的完整题目列表。读完后你将掌握：如何用复杂度表快速评估操作代价、如何在面试中识别数组题的套路、以及如何按仓库给出的优先级安排练习计划。

一、这份速查表在仓库中的位置与定位

数组是 Tech Interview Handbook 算法速查表板块的第一个基础主题。在 sidebars.js 中，algorithms/array 位于 "Algorithms study cheatsheets" 分类下 "Basics" 子分类的首位，与 string.md、hash-table.md、recursion.md、sorting-searching.md 并列。而在总览文档 study-cheatsheet.md 的主题优先级表中，Array 被标记为 High（高优先级），与 String、Sorting and searching、Matrix、Tree、Graph 同列。

原文档给出的定位结论值得直接引用：数组是面试中遇到的最常见数据结构，其他主题的题目也往往会涉及数组/序列，掌握数组对面试至关重要。 仓库的 8 周刷题计划数据 QuestionGroups.json 也印证了这一点——其中被标注 topic: "array" 的题目多达 11 道，是各主题中数量最多的之一。

二、数组基础：原理、优势与语言差异

2.1 核心定义

数组将同类型的值存储在连续的内存位置。处理数组时通常只关心两件事：元素的位置/下标（index） 和 元素本身。不同编程语言在底层对数组的实现方式不同，这会直接影响操作的真实时间复杂度。

原文档特别指出一个对面试准备很实际的语言差异：

• 在 Python（list）、JavaScript、Ruby、PHP 中，数组/列表的大小是动态的，创建时无需预先指定大小，因此在这些语言上做数组题通常更顺手；
• 在数组大小固定的语言中（如 C/Java 的固定长度数组），一旦元素数量超过容量，就必须分配一个新数组并把现有元素全部拷贝过去，这一步是 O(n) 的。

2.2 优势与劣势（原文档完整保留）

优势

• 用单个变量名存储多个同类型元素；
• 只要持有下标，元素访问就是 O(1) 快速操作——这与链表形成对比：链表必须从头节点开始遍历才能定位元素。

劣势

• 在数组中间插入/删除元素很慢：后续所有元素都要整体平移来腾出/填补位置。唯一的例外是插入/删除发生在数组末尾；
• 固定大小语言的数组初始化后无法原地扩容，扩容需要 O(n) 的重新分配与拷贝。

三、必须先分清的概念：Subarray vs Subsequence

原文档列出的两个高频术语，直接决定了题目难度的理解，必须严格区分：

术语	定义	示例（给定 [2, 3, 6, 1, 5, 4]）
Subarray（子数组）	数组中一段连续取值	[3, 6, 1] 是子数组；[3, 1, 5] 不是（不连续）
Subsequence（子序列）	删除若干（或不删）元素后、不改变剩余元素顺序得到的序列	[3, 1, 5] 是子序列；[3, 5, 1] 不是（顺序变了）

仓库中有一份可直接运行的参考实现 isSubsequence.js，用单指针扫描验证了"子序列只需保序、无需连续"的判定逻辑：

function isSubsequence(s, t) {
  if (s.length > t.length) {
    return false;
  }
  let matchedLength = 0;
  for (let i = 0; i < t.length; i++) {
    if (matchedLength < s.length && s[matchedLength] === t[i]) {
      matchedLength += 1;
    }
  }
  return matchedLength === s.length;
}

注意整个函数只遍历 t 一遍，匹配成功与否的时间复杂度都是 O(t.length)。

四、数组操作时间复杂度速查表（完整继承）

以下是原文档给出的完整复杂度表，建议直接背诵，面试白板推演时它是评估方案代价的第一依据：

操作	Big-O	说明
Access（按下标访问）	O(1)
Search（无序搜索）	O(n)
Search (sorted array)（有序数组搜索）	O(log n)	可二分
Insert（插入）	O(n)	插入后所有后续元素需整体右移一位
Insert (at the end)（末尾插入）	O(1)	无需移动其他元素的特例
Remove（删除）	O(n)	删除后所有后续元素需整体左移一位
Remove (at the end)（末尾删除）	O(1)	无需移动其他元素的特例

这张表解释了原文档"劣势"一节的成因：中间插入/删除 O(n) 的根源是连续内存 + 元素平移；而"末尾 O(1)"正是动态数组语言 append/pop 高效的理论基础。

五、面试中的三个注意事项（Things to look out for）

原文档给出的三条实战提醒，逐条展开：

1. 先澄清数组中是否存在重复值。 重复值的存在会影响答案吗？是让题目变简单还是变难？（例如去重类、两数之和类题目的去重逻辑完全取决于这一点。）
2. 用下标遍历数组时警惕越界。 循环边界 i < arr.length 与 i <= arr.length 的一字之差就是运行时错误。
3. 警惕代码中的切片（slice）与拼接（concatenate）。 这两种操作通常是 O(n)。尽可能用 start/end 下标来界定子数组/区间，而不是物理上切出一段新数组——这正是复杂度表中"Insert O(n)"思想在写码层面的体现。

六、边界条件（Corner cases）清单

提交前逐条自测，原文档给出的四类必查场景：

• 空序列；
• 只有 1 个或 2 个元素的序列；
• 含重复元素的序列；
• 序列中存在重复值。

仓库的参考实现也体现了这种边界意识：binarySearch.js 显式覆盖了 target 小于最小值、大于最大值、恰好命中边界下标等用例；mergeSort.js 的第一个分支 arr.length < 2 直接处理空数组与单元素数组这两个退化情形。

七、七大数组解题技巧（Techniques）深度解析

原文档开篇有一句关键总纲：数组和字符串都是序列（字符串就是字符数组），因此这里的大部分技巧同样适用于字符串题。 下面逐一保留并深化。

7.1 滑动窗口（Sliding Window）

适用于大量子数组/子串问题。窗口内两个指针通常朝同一方向移动、且永不相互越过，保证每个值最多被访问两次，时间复杂度仍为 O(n)。原文档推荐的代表题：Longest Substring Without Repeating Characters、Minimum Size Subarray Sum、Minimum Window Substring。

7.2 双指针（Two Pointers）

双指针是滑动窗口的更一般化版本：指针可以互相交叉、甚至可以分别位于两个不同的数组上。

• 单数组双指针代表题：Sort Colors（仓库数据中标注 routines: ["two-pointers"]，第 5 周，Medium）、Palindromic Substrings；
• 双数组双指针：处理两个数组时，常用"每个数组各一个下标"的方式遍历/比较，视情况递增其中一个指针——归并两个有序数组就是典型用法，代表题 Merge Sorted Array。

仓库的 mergeSort.js 中的 merge 函数正是双指针归并的最小可用实现，可以对照阅读：

function merge(arr1, arr2) {
  const merged = [];
  let i = 0, j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      merged.push(arr1[i]);
      i++;
    } else if (arr2[j] < arr1[i]) {
      merged.push(arr2[j]);
      j++;
    }
  }
  merged.push(...arr1.slice(i), ...arr2.slice(j));
  return merged;
}

7.3 从右向左遍历（Traversing from the right）

有时从数组右侧开始遍历比惯用的从左向右更简单。代表题：Daily Temperatures、Number of Visible People in a Queue。这类题的共同点是要找"下一个/上一个满足条件的元素"，反向扫描可以省去嵌套循环。

7.4 先排序（Sorting the array）

两个自问：

1. 数组是否有序或部分有序？ 若是，某种形式的二分搜索应该可行，这通常也意味着面试官期待一个快于 O(n) 的解法；
2. 能否先排序再解题？ 排序常常能显著简化问题——前提是题目不要求保持原元素顺序。代表题：Merge Intervals、Non-overlapping Intervals。

仓库的二分搜索实现 binarySearch.js 值得作为白板模板收藏（mid = left + floor((right - left) / 2) 的写法避免溢出）：

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) {
      return mid;
    }
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

7.5 前处理/预处理（Precomputation）

凡涉及子数组求和/求积的题目，用哈希或前缀和/前缀积、后缀和/后缀积做预计算往往能一步到位。代表题：Product of Array Except Self、Minimum Size Subarray Sum，以及 LeetCode 官方"prefix-sum"标签下的全部题目。

Product of Array Except Self 正是"双向前缀扫描"的经典落地：一遍正向记录前缀积、一遍反向记录后缀积，全程 O(n) 时间、O(1) 额外空间（不计输出）。

7.6 下标即哈希键（Index as a hash key）

当题目给定一个序列且要求 O(1) 额外空间时，可以把数组本身当作哈希表来用。原文档给出的经典手法：若数组只含 1 到 N 的值（N 为数组长度），就把对应下标（值减一）位置的值取负来标记该数字出现过。代表题：First Missing Positive、Daily Temperatures。

7.7 多次遍历数组（Traversing more than once）

这一点显而易见但常被忽略：遍历两遍、三遍（只要次数小于 n 次）总复杂度仍然是 O(n)。有时多遍历一两遍反而能让思路更清晰且保持 O(n)。

八、完整题单：必刷 + 进阶练习

8.1 必刷题目（Essential questions）

原文档标注的 4 道核心题，学完本主题后必须动手练习：

题目	仓库数据佐证	关联技巧
Two Sum	QuestionGroups.json 第 1 周，Easy，routines: ["hashing"]	哈希
Best Time to Buy and Sell Stock	第 1 周，Easy	单遍扫描维护最值
Product of Array Except Self	第 4 周，Medium，routines: ["prefix-sum"]	7.5 预处理
Maximum Subarray	第 3 周，Medium	单遍状态维护

8.2 进阶练习题目（Recommended practice questions）

完成必刷题之后的进阶清单，共 6 道：

• Contains Duplicate（仓库数据：第 2 周，Easy，routines: ["hash-table", "sorting"]）
• Maximum Product Subarray
• Search in Rotated Sorted Array（仓库数据：第 4 周，Medium；对应技巧 7.4 的"部分有序 → 变体二分"）
• 3Sum（仓库数据：第 3 周，Medium，routines: ["two-pointers"]）
• Container With Most Water（仓库数据：第 6 周，Medium，routines: ["greedy", "two-pointers"]）
• Sliding Window Maximum

8.3 仓库 8 周计划中所有 Array 主题题目

从 QuestionGroups.json 中按 topic: "array" 过滤出的完整清单（含建议时长），可作为排期参考：

周次	题目	难度	时长	标注技巧
Week 1	Two Sum	Easy	15 min	hashing
Week 1	Best Time to Buy and Sell Stock	Easy	20 min	—
Week 2	Majority Element	Easy	20 min	sorting
Week 2	Contains Duplicate	Easy	15 min	hash-table, sorting
Week 3	Insert Interval	Medium	25 min	interval
Week 3	3Sum	Medium	30 min	two-pointers
Week 4	Product of Array Except Self	Medium	30 min	prefix-sum
Week 5	Combination Sum	Medium	30 min	backtracking
Week 5	Merge Intervals	Medium	30 min	interval
Week 5	Sort Colors	Medium	25 min	two-pointers
Week 6	Container With Most Water	Medium	35 min	greedy, two-pointers

注意 Interval 类题目（Insert Interval、Merge Intervals）虽然归在 array 主题下，但 QuestionGroups.json 中它们同时带有 interval 标签——练习时可结合仓库的 interval.md 一起看；区间合并的核心原语可参考 intervalsMerge.js（两个重叠区间合并为 [min(start), max(end)]）。

九、学习资源与课程（Learning resources & courses）

原文档附带的资源部分，按原文完整保留（此处按输出规范去掉外部链接，仅保留资源名称供自行检索）：

阅读与视频

• 文章：Guru99 的 "Array in Data Structure: What is, Arrays Operations"
• 视频：加州大学圣地亚哥分校（UC San Diego）Coursera 数据结构课程的 Arrays 一课

推荐课程（引自文档引用的 AlgorithmCourses.md）

1. AlgoMonster：由 Google 工程师打造，以数据驱动方式教授最高价值的题目模式，附带数据结构与算法速览内容，一次性付费、终身访问；
2. Grokking the Coding Interview: Patterns for Coding Questions（Design Gurus）：从"题目模式"视角组织练习，支持 Java、Python、C++、JavaScript 多种语言并附分步可视化，主张"学模式而非背答案"；
3. Master the Coding Interview: Data Structures + Algorithms（Udemy）：约 19 小时内容，除算法外还覆盖简历、非技术面试与谈薪，编码演示使用 JavaScript。

十、总结：把这份速查表用起来

回到原文档的核心信息链：数组 = 面试第一优先级数据结构（High）→ 记住 O(1) 访问/O(n) 中间增删的复杂度表 → 用 Subarray 与 Subsequence 的正确定义审题 → 按"滑窗、双指针、反向遍历、排序、预处理、下标当哈希、多次遍历"七个套路找解法 → 完成 4 道必刷题 + 6 道进阶题 → 按 8 周计划补足 11 道 Array 主题题。 这份文档与 study-cheatsheet.md 的总览、QuestionGroups.json 的排期数据、experimental/utilities/javascript 下的可运行参考实现共同构成一个自洽的学习闭环：概念、技巧、题单、代码样例各司其职，建议按此顺序对照练习。