八个数学点助你 LeetCode 高效刷题

还在为 LeetCode 上的数学题头疼吗？许多算法问题的根基，其实就藏在我们曾经学过的数学里。本文将为你系统梳理 8 个在算法面试中至关重要的数学知识点，从复杂度分析到数论技巧，助你扫清障碍，高效刷题。

引言：你的代码里，藏着数学的影子

你是否也曾有过这样的经历：在 LeetCode 上遇到一道中等难度的题目，绞尽脑汁，却发现最优解的思路竟然源于一个看似简单却被遗忘的数学公式？

算法与数学，本就是一对密不可分的兄弟。尤其是在以 LeetCode 为代表的编程面试中，许多问题的考察点，并非是多么高深的算法理论，而是能否灵活运用基础的数学知识来分析问题、优化代码。

好消息是，你并不需要成为数学家才能攻克这些题目。大多数时候，我们需要的仅仅是那些躺在课本里、既熟悉又陌生的知识点。本文将带你重拾这些“神兵利器”，让你在算法的世界里如虎添翼。

一、万丈高楼平地起：复杂度分析与基本数列

这两部分是你分析和理解算法效率的基石。

1. 对数 ($O(\log n)$) 与指数 ($O(2^n)$)：你的时间复杂度标尺

在算法世界，我们用时间复杂度来衡量代码的效率。对数和指数函数，正是这把标尺上两个至关重要的刻度。

对数时间复杂度 $O(\log n)$：代表了最优秀的算法之一。如果你的算法在每一步都能将问题的规模缩小一半（或任意固定比例），那么它的时间复杂度就是对数级别的。

核心场景：二分查找 (Binary Search)。

LeetCode 实战：在一个有序数组 nums 中查找 target。

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2 # 防止溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

指数时间复杂度 $O(2^n)$：通常意味着“暴力穷举”。当问题需要你探索所有可能性时，就可能遇到它。这通常是优化的起点。
- 核心场景：回溯算法求所有子集。
- LeetCode 实战：求集合 [1, 2, 3] 的所有子集。每个元素都有“选”与“不选”两种状态，共 $2^3 = 8$ 个子集。

2. 等差与等比数列：识别代码中的隐藏规律

许多算法题本质上是在让你“找规律”，而数列就是规律最纯粹的数学表达。

等差数列：公差恒定。最著名的例子莫过于高斯计算 $1+2+…+100$。
- 核心公式：求和 $S_n = \frac{n(a_1 + a_n)}{2}$。
- LeetCode 实战：在 “缺失的数字” (LeetCode 268) 这类题目中，利用求和公式可以迅速算出完整数组的和，再减去现有数组的和，差值即为缺失的数字，这比循环累加更优雅高效。
等比数列：公比恒定。常用于涉及“翻倍”或“减半”的场景。
- LeetCode 实战：当你遇到涉及二进制（每次*2或/2）、或者类似细胞分裂、复利计算的模型时，就应该警惕等比数列的存在。

二、克敌制胜的利器：核心数学工具箱

掌握了基础，我们还需要一些强大的工具来解决特定领域的问题。

3. 数论三剑客：质数、公约数与模运算

数论是整数世界的法则，也是算法题的常客。

质数：除了1和它本身，不能被其他自然数整除的数。
- 应用：判断质数、筛法求一定范围内的质数（如埃氏筛）。
最大公约数 (GCD)：求 GCD 请务必掌握欧几里得算法（辗转相除法），它是数论算法的基石。
- 应用：分数化简、处理周期性问题。
模运算 (%)：求余数。它是处理大数问题和循环问题的终极武器。
- 黄金法则：$(a + b) \pmod m = ((a \pmod m) + (b \pmod m)) \pmod m$。
- 应用：几乎所有要求“结果对 $10^9 + 7$ 取模”的题目；快速幂算法；判断链表是否有环。

4. 排列组合：当回溯与 DP 遇上数学

计数问题、子集问题、排列问题，都离不开排列组合的思想。

排列 (Permutation, $P_n^k$)：顺序很重要。
- 应用：求全排列。常与回溯算法结合。
组合 (Combination, $C_n^k$)：顺序不重要。
- 应用：求子集、组合总和。常与回溯或动态规划结合。

5. 位运算：直达计算机底层的魔法

位运算允许你直接在二进制层面操作数据，速度极快，是许多“骚操作”的来源。

核心操作：& (与), | (或), ^ (异或), << (左移), >> (右移)。
杀手级应用：异或(^)运算
- 性质：x ^ x = 0, x ^ 0 = x。
- LeetCode 实战：“只出现一次的数字” (LeetCode 136)。将数组中所有数字进行异或操作，最终结果就是那个只出现一次的数字。
1
2
3
4
5
def single_number(nums):
result = 0
for num in nums:
result ^= num
return result

6. 平面几何：当算法题来到二维空间

虽然不如前面几位高频，但几何题一旦出现，没有准备会非常棘手。

核心：平面直角坐标系。
关键公式：两点间距离公式 $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$。
应用：求 K 个离原点最近的点、判断多个点是否共线等。

三、总结：如何将数学知识转化为代码

数学知识点	相关算法/应用场景	重要性
指数/对数函数	时间/空间复杂度分析（如 $O(\log n)$, $O(2^n)$), 二分查找	★★★★★
等差/等比数列	规律查找、数组求和、特定模式的数值计算	★★★★☆
质数/合数	整数问题、筛法求质数、因数分解	★★★★☆
最大公约数/最小公倍数	周期性问题、分数运算、数论问题（欧几里得算法）	★★★★☆
模运算	大数求余、快速幂、防止溢出、循环/周期判断	★★★★★
排列组合	回溯算法（全排列、子集、组合）、动态规划	★★★★★
平面几何	坐标系问题、距离计算、斜率判断	★★★☆☆
位运算	高效计算、状态压缩、特定整数问题（如找唯一数）	★★★★★

最后的建议：

问题驱动学习：不要为了学数学而学数学。遇到一道题，卡住了，发现需要某个数学知识，再去深入学习它。这样的学习效率最高，印象也最深刻。
理解重于记忆：理解为什么二分查找是 $O(\log n)$，比死记硬背这个结论重要一万倍。理解能让你举一反三。
从现在开始：打开 LeetCode，找一道简单的数学题，比如 “判断一个数是否为 2 的幂”，尝试用位运算来解决它。你会立刻感受到数学与代码结合的魅力。

数学不是你刷题路上的拦路虎，而是你手中最锋利的剑。祝你在算法的世界里，所向披靡！