从百钱百鸡到LeetCode：枚举算法的智慧与实战进化

在编程学习的道路上，我们常常会遇到这样的困惑：为什么看似"笨拙"的枚举法有时能轻松解决问题，有时却导致程序卡死？这个问题困扰着无数初学者。让我们从一个流传千年的数学趣题出发，逐步揭开枚举算法的神秘面纱，探索它在现代算法题中的巧妙应用。

1. 百钱百鸡：枚举法的经典启蒙

公元5世纪，《张丘建算经》记载了这样一道题："鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？"这道题堪称枚举算法的最佳教学案例。

1.1 最朴素的枚举实现

我们先看最直接的解法——三重循环遍历所有可能性：

def buy_chicken_naive():
    for x in range(101):      # 公鸡数量
        for y in range(101):  # 母鸡数量
            for z in range(101):  # 小鸡数量
                if z % 3 == 0 and 5*x + 3*y + z//3 == 100 and x + y + z == 100:
                    print(f"公鸡{x}只，母鸡{y}只，小鸡{z}只")

这个解法虽然正确，但循环次数高达101×101×101=1,030,301次，效率极低。这正展示了枚举法最显著的特点： 简单直接但可能效率低下 。

1.2 优化枚举范围的智慧

观察题目特征，我们可以做出关键优化：

1. 根据总金额限制，公鸡最多20只（100÷5）
2. 母鸡最多33只（100÷3）
3. 小鸡数量可由总数推导：z = 100 - x - y

优化后的代码：

def buy_chicken_optimized():
    for x in range(21):       # 公鸡不超过20只
        for y in range(34):   # 母鸡不超过33只
            z = 100 - x - y
            if z % 3 == 0 and 5*x + 3*y + z//3 == 100:
                print(f"公鸡{x}只，母鸡{y}只，小鸡{z}只")

优化后循环次数降至21×34=714次，效率提升1400多倍！这个案例教会我们枚举法的第一个优化原则： 通过问题约束缩小枚举范围 。

2. LeetCode实战：枚举法的现代应用

将目光转向现代编程面试，枚举法依然是解决许多问题的有效工具。让我们看几个典型例子。

2.1 两数之和：从暴力到哈希的进化

LeetCode第1题"两数之和"是枚举法的经典应用场景：

给定整数数组nums和目标值target，找出和为target的两个数的下标

暴力枚举解法

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

这种解法时间复杂度O(n²)，对于大规模数据(如n=10⁴)会超时。但作为第一思路，它简单直接，适合作为解题起点。

哈希表优化

利用哈希表存储已遍历元素，可将时间复杂度降至O(n)：

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

这个优化展示了枚举法的进阶思路： 用空间换时间，通过数据结构减少重复计算 。

2.2 计数质数：筛选法的威力

LeetCode第204题要求统计小于n的质数数量。最直接的枚举思路是对每个数检查是否为质数：

def countPrimes(n):
    def is_prime(x):
        if x < 2: return False
        for i in range(2, int(x**0.5)+1):
            if x % i == 0:
                return False
        return True
    
    return sum(1 for x in range(2, n) if is_prime(x))

虽然通过√n优化了单次检查，但整体复杂度仍达O(n√n)。更高效的埃拉托斯特尼筛法展示了枚举的另一种优化方向：

def countPrimes(n):
    if n <= 2: return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i:n:i] = [False] * len(is_prime[i*i:n:i])
    return sum(is_prime)

这个算法的核心思想是： 通过预处理信息，避免重复枚举 ，将复杂度降至O(n log log n)。

3. 枚举算法的优化方法论

从上述案例中，我们可以总结出枚举算法的优化路径：

3.1 缩小枚举范围

• 利用问题约束 ：如百钱百鸡中根据价格限制数量范围
• 数学推导 ：通过等式关系减少变量（如z=100-x-y）
• 边界分析 ：确定各变量的合理取值范围

3.2 减少重复计算

• 记忆化存储 ：如两数之和中的哈希表优化
• 预处理信息 ：如质数筛法提前标记非质数
• 排序剪枝 ：对有序数据提前终止不必要的枚举

3.3 转换枚举维度

• 改变枚举顺序 ：有时逆向枚举更高效
• 分层枚举 ：先枚举关键变量，再推导其他
• 对称性利用 ：避免重复枚举本质相同的状态

4. 何时选择枚举算法？

虽然枚举法常被视为"最后手段"，但在以下场景中它可能是最佳选择：

1. 问题规模较小时 ：当n<1000时，O(n²)的算法依然可行
2. 作为验证工具时 ：用来验证更复杂算法的正确性
3. 多解需要全列举时 ：如组合问题需要所有可能解
4. 与其他算法配合时 ：如动态规划中的状态枚举

在实际编程中，我常采用这样的解题流程：

1. 先用枚举法写出基础解，确保理解问题
2. 分析枚举过程中的冗余计算
3. 逐步引入优化手段
4. 必要时转向更高级的算法

这种"从枚举出发，向优化迈进"的方法，既能保证解题的可靠性，又能培养算法优化思维。