cswork / 模板打开 500 路题单

第 01 站 · 线性结构

数组原地操作与排序

读写双指针原地压缩 时间 O(n) · 空间 O(1)

打开 500 路题单 · 第 01 站 · 20 题
先学
起点站，不需要先修。
学完去
面试频次
5 家公司考过 · 面经出现 9 次Meta 3、Apple 2、Microsoft 2、Amazon 1、Walmart Labs 1

先做这道

LC 26删除有序数组中的重复项简单
卡住再看

用读写双指针维护已去重前缀，明确返回长度与有效区间。

要点

  1. 写指针 w 左边是已经确定保留的结果；读指针只往前扫，两个指针都只走一遍。
  2. 判断能不能保留时和 nums[w-k] 比，也就是和「结果」比，而不是和上一个读到的原始元素比。
  3. 原地合并两个有序数组时从尾部往前写，就不会覆盖还没读到的数据。

易错点

  • 题目要的是新长度，判题只看前 k 个位置；返回数组本身或者去比较 k 之后的内容都会出错。
  • 边遍历边删除（Python 的 list.remove、Java 的 ArrayList.remove）是 O(n²)，还会跳过元素。
  • 排序比较器写成 a - b，值接近 ±2^31 时会溢出；用 Integer.compare 或直接比较大小。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

数组 · 插入、删除与原地去重

有序数组 1, 2, 2, 4, 4, 4, 6：插入 3，删除下标 0，再去重

换个输入
10
21
22
43
44
45
66
·7
当前处理已发现 / 已计算答案
长度
7
搬移次数
0
w
—
r
—

一个有序数组，末尾留了一个空位（·）。数组在内存里是连续的，插入和删除都要搬动后面的元素。

始终成立数组始终连续存放：中间插入或删除要搬动后面的元素；去重时 w 左边就是最终结果。

交互演示 · 逐步观察

快速排序 · 平均 O(n log n)，有序时 O(n²)

把 2, 3, 1, 2, 3, 1 从小到大排序

换个输入
2#0
3#1
1#2
2#3
3#4
1#5
当前处理已发现 / 已计算答案
比较
0
交换/写入
0

小字 #i 是每个数原来的下标：排完后，相同的数如果 #i 不再从小到大，这个排序就不稳定。

始终成立分区后基准落在最终位置：左边都比它小，右边都不比它小。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 26。

Python
def keep_at_most(nums: list[int], k: int) -> int:
    """Sorted nums: keep each value at most k times, in place. Returns the new length."""
    w = 0  # nums[:w] is the kept prefix
    for x in nums:
        if w < k or nums[w - k] != x:
            nums[w] = x
            w += 1
    return w
C++
// Sorted nums: keep each value at most k times, in place. Returns the new length.
int keepAtMost(vector<int>& nums, int k) {
    int w = 0;  // nums[0, w) is the kept prefix
    for (int x : nums)
        if (w < k || nums[w - k] != x) nums[w++] = x;
    return w;
}
Java
class Solution {
    // Sorted nums: keep each value at most k times, in place. Returns the new length.
    int keepAtMost(int[] nums, int k) {
        int w = 0; // nums[0, w) is the kept prefix
        for (int x : nums)
            if (w < k || nums[w - k] != x) nums[w++] = x;
        return w;
    }
}
Go
// keepAtMost keeps each value of sorted nums at most k times, in place,
// and returns the new length.
func keepAtMost(nums []int, k int) int {
	w := 0 // nums[:w] is the kept prefix
	for _, x := range nums {
		if w < k || nums[w-k] != x {
			nums[w] = x
			w++
		}
	}
	return w
}

常见变体

这一站的题还会用到下面 3 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

三指针荷兰国旗划分时间 O(n) · 空间 O(1)

数组里只有三种值（0/1/2，或「小于 / 等于 / 大于 pivot」）要原地分成三段：lo 左边全是 0，hi 右边全是 2，i 扫中间；和 hi 交换后 i 不前进，因为换过来的值还没看过。LC 75 颜色分类就是它，快排的三路划分也是。

Python
def sort_colors(nums: list[int]) -> None:
    """Sorts 0s, 1s and 2s in place in one pass."""
    lo, i, hi = 0, 0, len(nums) - 1  # nums[:lo] are 0, nums[lo:i] are 1, nums[hi+1:] are 2
    while i <= hi:
        if nums[i] == 0:
            nums[lo], nums[i] = nums[i], nums[lo]
            lo += 1
            i += 1
        elif nums[i] == 2:
            nums[i], nums[hi] = nums[hi], nums[i]
            hi -= 1  # i stays: the value swapped in is not checked yet
        else:
            i += 1
C++
// Sorts 0s, 1s and 2s in place in one pass.
void sortColors(vector<int>& nums) {
    int lo = 0, i = 0, hi = (int)nums.size() - 1;  // [0, lo) are 0, [lo, i) are 1, (hi, n) are 2
    while (i <= hi) {
        if (nums[i] == 0) swap(nums[lo++], nums[i++]);
        else if (nums[i] == 2) swap(nums[i], nums[hi--]);  // i stays: the value swapped in is not checked yet
        else i++;
    }
}
Java
class Solution {
    // Sorts 0s, 1s and 2s in place in one pass.
    void sortColors(int[] nums) {
        int lo = 0, i = 0, hi = nums.length - 1; // [0, lo) are 0, [lo, i) are 1, (hi, n) are 2
        while (i <= hi) {
            if (nums[i] == 0) swap(nums, lo++, i++);
            else if (nums[i] == 2) swap(nums, i, hi--); // i stays: the value swapped in is not checked yet
            else i++;
        }
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
Go
// sortColors sorts 0s, 1s and 2s in place in one pass.
func sortColors(nums []int) {
	lo, i, hi := 0, 0, len(nums)-1 // [0, lo) are 0, [lo, i) are 1, (hi, n) are 2
	for i <= hi {
		switch nums[i] {
		case 0:
			nums[lo], nums[i] = nums[i], nums[lo]
			lo++
			i++
		case 2:
			nums[i], nums[hi] = nums[hi], nums[i]
			hi-- // i stays: the value swapped in is not checked yet
		default:
			i++
		}
	}
}
原地哈希：把值 v 换到下标 v - 1时间 O(n)（每次交换让一个值归位）· 空间 O(1)

值落在 1..n 之间、要求 O(1) 额外空间找缺失或重复的数：把每个值反复换到它「该在」的位置，之后再扫一遍，第一个不在家的位置就是答案。LC 41 缺失的第一个正数、LC 448、LC 442、LC 645 都是这个形状。

Python
def first_missing_positive(nums: list[int]) -> int:
    """Smallest positive integer not in nums, in O(1) extra space."""
    n = len(nums)
    for i in range(n):
        # Swap nums[i] home to index v - 1 until it is out of range or already there.
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            v = nums[i]
            nums[i], nums[v - 1] = nums[v - 1], v
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1
C++
// Smallest positive integer not in nums, in O(1) extra space.
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++)
        // Swap nums[i] home to index v - 1 until it is out of range or already there.
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) swap(nums[i], nums[nums[i] - 1]);
    for (int i = 0; i < n; i++)
        if (nums[i] != i + 1) return i + 1;
    return n + 1;
}
Java
class Solution {
    // Smallest positive integer not in nums, in O(1) extra space.
    int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++)
            // Swap nums[i] home to index v - 1 until it is out of range or already there.
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int v = nums[i];
                nums[i] = nums[v - 1];
                nums[v - 1] = v;
            }
        for (int i = 0; i < n; i++)
            if (nums[i] != i + 1) return i + 1;
        return n + 1;
    }
}
Go
// firstMissingPositive returns the smallest positive integer not in nums, in O(1) extra space.
func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := range nums {
		// Swap nums[i] home to index v - 1 until it is out of range or already there.
		for nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
			v := nums[i]
			nums[i], nums[v-1] = nums[v-1], v
		}
	}
	for i, v := range nums {
		if v != i+1 {
			return i + 1
		}
	}
	return n + 1
}
Kadane：以当前元素结尾的最大和时间 O(n) · 空间 O(1)

求和最大的连续子数组（LC 53）：只记「以当前元素结尾」的最好和，它要么接上前面，要么从自己重新开始；全局答案取历史最大。全是负数时答案是最大的那个负数，所以初值用 nums[0] 而不是 0。

Python
def max_subarray(nums: list[int]) -> int:
    """Largest sum of a non-empty contiguous subarray."""
    best = cur = nums[0]  # cur: best sum of a subarray ending at the current element
    for x in nums[1:]:
        cur = max(x, cur + x)  # extend, or start over at x
        best = max(best, cur)
    return best
C++
// Largest sum of a non-empty contiguous subarray.
long long maxSubarray(const vector<int>& nums) {
    long long best = nums[0], cur = nums[0];  // cur: best sum of a subarray ending here
    for (size_t i = 1; i < nums.size(); i++) {
        cur = max<long long>(nums[i], cur + nums[i]);  // extend, or start over
        best = max(best, cur);
    }
    return best;
}
Java
class Solution {
    // Largest sum of a non-empty contiguous subarray.
    long maxSubarray(int[] nums) {
        long best = nums[0], cur = nums[0]; // cur: best sum of a subarray ending here
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]); // extend, or start over
            best = Math.max(best, cur);
        }
        return best;
    }
}
Go
// maxSubarray returns the largest sum of a non-empty contiguous subarray.
func maxSubarray(nums []int) int {
	best, cur := nums[0], nums[0] // cur: best sum of a subarray ending here
	for _, x := range nums[1:] {
		cur = max(x, cur+x) // extend, or start over at x
		best = max(best, cur)
	}
	return best
}

为什么对

  1. 不变式：每一步开始时，nums[0..w) 恰好是已扫描部分 nums[0..r) 里该保留的元素，顺序不变。nums[r] 要保留就写到 w 再 w++，不变式依然成立；r 扫到末尾时 nums[0..w) 就是答案。
  2. 写入不会覆盖还没读的数据：始终有 w ≤ r，写入的格子一定已经读过。
  3. 从后往前合并两个有序数组：写指针 k = i + j + 1，只要 nums2 还没写完（j ≥ 0）就有 k > i，nums1 里没读的部分不会被覆盖。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文
这类题我用读写双指针。读指针 r 从左到右扫一遍，写指针 w 左边永远是已经确定的结果。遇到要保留的元素就写到 w 再右移 w，因为 w 不会超过 r，所以不会覆盖还没读的数据。整体一遍扫描，时间 O(n)，额外空间 O(1)。
English
I use a read pointer and a write pointer. The read pointer scans left to right once, and everything left of the write pointer is final. When an element should be kept, I copy it to the write position and advance it; since the write pointer never passes the read pointer, nothing unread is overwritten. That is one pass, O(n) time and O(1) extra space.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。 只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）
这道题你会了吗？

小测

5 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。 去 OA 选择题练习

5 道题
  1. 在长度为 n 的动态数组（如 Python list）下标 0 处插入一个元素，时间复杂度是？
  2. 动态数组满了以后按倍数扩容（比如容量翻倍），而不是每次固定多开 100 个位置，主要是为了什么？
  3. 下面代码的时间复杂度是？（n = len(a)，取最紧的界）
    def reverse_copy(a):
    out = []
    for x in a:
        out.insert(0, x)
    return out
  4. 下面代码的时间复杂度是？（取最紧的界）
    def build(n):
    a = []
    for i in range(n):
        a.append(i)
    return a
  5. 下面代码的时间复杂度是？（n = len(a)，取最紧的界）
    def normalize(a):
    return [x / max(a) for x in a]

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

分档练习

本站在 500 路里的 20 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 7

#题目一句话思路难度分
26删除有序数组中的重复项用读写双指针维护已去重前缀，明确返回长度与有效区间。
27移除元素在不保序约束下比较覆盖写入与末尾交换两种删除策略。
88合并两个有序数组从后向前合并两个有序数组，避免覆盖尚未读取的数据。
283移动零稳定压缩非零元素，再填补尾部，区分稳定性与额外空间。
350两个数组的交集 II比较计数哈希与排序双指针求多重集合交集，保留重复次数。
169多数元素用抵消思想识别多数元素，说明多数存在的前提。
645错误的集合结合频次或原地标记定位一个重复值与一个缺失值。

核心 10

#题目一句话思路难度分
80删除有序数组中的重复项 II把去重推广到每个值最多保留两次，维护写指针不变量。
75颜色分类用三路划分维护小于、等于、大于基准的连续区间。
48旋转图像通过转置与翻转实现原地旋转，检查行列下标映射。
229多数元素 II推广投票法并二次验证候选者，避免把候选当作答案。
238除了自身以外数组的乘积分离前缀积和后缀积，在含零输入下避免除法。
448找到所有数组中消失的数字利用值域与下标的对应关系实现原地存在性标记。
442数组中重复的数据通过原地符号标记识别重复值，处理重复访问的含义。
912排序数组实现可靠排序并比较归并与快排的稳定性、空间和最坏复杂度。
334递增的三元子序列维护最小一元和二元候选，在线判断递增三元组。
53最大子数组和用前缀和减去历史最小前缀求最大子数组，并处理全负数。

进阶 3

#题目一句话思路难度分
41缺失的第一个正数把正整数放回对应位置，在常数额外空间中寻找首个缺失值。
287寻找重复数将数组映射理解为函数图，用快慢指针在不修改数组时寻找重复值。
324摆动排序 II结合中位数划分与位置重映射构造严格交错排列。

本站 OA 真题 181

全部 181 道

Core Skills

不调库，亲手实现这一站用到的数据结构或算法，四种语言都能判题。