Algorithms study cheatsheets

Coding interview 的 Array cheatsheet

Array 学习指南，包含练习题、技巧、时间复杂度与推荐资源

Introduction

Array 在连续内存中存储相同类型的值。使用 array 时，通常关注两件事：元素的 index/position，以及元素本身。不同语言对 array 的底层实现不同，会影响操作的 time complexity。在 Python、JavaScript、Ruby、PHP 等语言里，array（Python 里叫 list）是动态大小，不需要预先指定长度，所以面试中更容易使用。

Array 是面试中最常见的数据结构之一。很多其他题目也会涉及数组/序列。掌握 array 是面试必备。

Advantages

用一个变量名存储多个同类型元素
已知 index 时访问非常快；而 linked list 需要从头遍历

Disadvantages

在数组中间插入/删除元素很慢，因为需要移动其他元素。例外是插入/删除发生在数组末尾。
在固定长度数组的语言里，初始化后长度不可变。如果插入导致超出容量，需要分配新数组并复制元素，时间为 O(n)。

Learning resources

Readings
- Array in Data Structure: What is, Arrays Operations, Guru99
Videos
- Arrays, University of California San Diego

Common terms

做 array 题时常见术语：

Subarray - 数组中连续的一段。
- Example: [2, 3, 6, 1, 5, 4] 里 [3, 6, 1] 是 subarray，[3, 1, 5] 不是。
Subsequence - 删除部分或不删除元素，但保留顺序的序列。
- Example: [2, 3, 6, 1, 5, 4] 里 [3, 1, 5] 是 subsequence，[3, 5, 1] 不是。

Time complexity

Operation	Big-O	Note
Access	O(1)
Search	O(n)
Search (sorted array)	O(log(n))
Insert	O(n)	插入时需要把后续元素整体右移一位，耗时 O(n)
Insert (at the end)	O(1)	在末尾插入，不需要移动元素
Remove	O(n)	删除时需要把后续元素整体左移一位，耗时 O(n)
Remove (at the end)	O(1)	在末尾删除，不需要移动元素

面试时需要注意

澄清数组是否有重复值。重复值会影响答案吗？让题更简单还是更难？
用 index 遍历时，注意不要越界。
注意 slicing 或拼接数组的成本。切片/拼接通常是 O(n)。可以用 start/end index 代替实际切片。

Corner cases

Empty sequence
只有 1 或 2 个元素
元素重复
有重复值

Techniques

Array 和 string 都是序列（string 也是字符数组），所以这里很多技巧也适用于 string。

Sliding window

掌握 sliding window technique，适用于很多 subarray/substring 题。sliding window 的双指针通常同向移动且不会交叉，因此每个元素最多访问两次，时间仍是 O(n)。Examples: Longest Substring Without Repeating Characters, Minimum Size Subarray Sum, Minimum Window Substring

Two pointers

Two pointers 是 sliding window 的泛化版本，指针可以交叉，也可以在两个数组上。Examples: Sort Colors, Palindromic Substrings

给两个数组时，常用各自一个指针来遍历/比较，按情况移动其中一个。例如 merge 两个 sorted arrays。Examples: Merge Sorted Array

从右往左遍历

有些题从右往左遍历更方便。Examples: Daily Temperatures, Number of Visible People in a Queue

排序数组

数组是否已排序/部分排序？如果是，通常可以用 binary search（优于 O(n)）。
能否先排序？排序后可能大幅简化问题，但如果要保留原顺序就不行。Examples: Merge Intervals, Non-overlapping Intervals

Precomputation

涉及子数组求和/求积时，可用 prefix/suffix sum/product 预计算。Examples: Product of Array Except Self, Minimum Size Subarray Sum, LeetCode questions tagged "prefix-sum"

用 index 作为 hash key

若题目要求 O(1) space，可考虑用数组本身当 hash table。例如数组值范围为 1..N，N 是长度，则可用 “在 index 处取负” 表示出现。Examples: First Missing Positive, Daily Temperatures

多次遍历数组

遍历数组两次/三次（小于 n 次）仍然是 O(n)。有时多遍历能让你保持 O(n) 的同时解决问题。

Essential questions

这些是该 topic 必练题。