7.1 枚举算法 --- 1. 枚举算法简介枚举算法（Enumeration Algorithm），又称穷举算法，是指根据问题的特点，逐一列出所有可能的解，并与目标条件进行比较，找出满足要求的答案。枚举时要确保不遗漏、不重复。
枚举算法的核心思想就是：遍历所有可能的状态，逐个判断是否满足条件，找到符合要求的解。
由于需要遍历所有状态，枚举算法在问题规模较大时效率较低。但它也有明显优点：
实现简单，易于编程和调试。基于穷举所有情况，正确性容易验证。因此，枚举算法常用于小规模问题，或作为其他算法的辅助工具，通过枚举部分信息来提升主算法的效率。
2. 枚举算法的解题思路2.1 枚举算法的解题思路枚举算法是最简单、最基础的搜索方法，通常是遇到问题时的首选方案。
由于实现简单，我们可以先用枚举算法尝试解决问题，再考虑是否需要优化。
枚举算法的基本步骤如下：
明确需要枚举的对象、枚举范围和约束条件。逐一枚举所有可能情况，判断是否满足题意。思考如何提升枚举效率。提升效率的常用方法有：
抓住问题本质，尽量缩小状态空间。增加约束条件，减少无效枚举。利用某些问题特有的性质（例如对称性等），避免重复计算。2.2 枚举算法的简单应用以经典的「百钱买百鸡问题」为例：
问题：公鸡 5 元/只，母鸡 3 元/只，小鸡 1 元/3 只。用 100 元买 100 只鸡，问各买多少只？
解题步骤：
确定枚举对象和范围
枚举对象：公鸡数 xxx，母鸡数 yyy，小鸡数 zzz枚举范围：0≤x,y,z≤1000 \le x, y, z \le 1000≤x,y,z≤100约束条件：5x+3y+z3=1005x + 3y + \frac{z}{3} = 1005x+3y+3z=100 且 x+y+z=100x + y + z = 100x+y+z=100暴力枚举
class Solution:
def buyChicken(self):
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("公鸡 %s 只，母鸡 %s 只，小鸡 %s 只" % (x, y, z))优化枚举效率
利用 z=100−x−yz = 100 - x - yz=100−x−y 减少一重循环缩小枚举范围：x∈[0,20]x \in [0, 20]x∈[0,20]，y∈[0,33]y \in [0, 33]y∈[0,33]class Solution:
def buyChicken(self):
for x in range(21):
for y in range(34):
z = 100 - x - y
if z % 3 == 0 and 5 * x + 3 * y + z // 3 == 100:
print("公鸡 %s 只，母鸡 %s 只，小鸡 %s 只" % (x, y, z))3. 枚举算法的应用3.1 经典例题：两数之和3.1.1 题目链接1. 两数之和 - 力扣（LeetCode）3.1.2 题目大意描述：给定一个整数数组 numsnumsnums 和一个整数目标值 targettargettarget。
要求：在该数组中找出和为 targettargettarget 的两个整数，并输出这两个整数的下标。可以按任意顺序返回答案。
说明：
2≤nums.length≤1042 \le nums.length \le 10^42≤nums.length≤104。−109≤nums[i]≤109-10^9 \le nums[i] \le 10^9−109≤nums[i]≤109。−109≤target≤109-10^9 \le target \le 10^9−109≤target≤109。只会存在一个有效答案。示例：
示例 1：输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：输入：nums = [3,2,4], target = 6
输出：[1,2]3.1.3 解题思路思路 1：枚举算法通过两重循环，依次枚举数组中所有可能的下标对 (i,j)(i, j)(i,j)（其中 i def twoSum(self, nums: List[int], target: int) -> List[int]: # 遍历第一个数的下标 for i in range(len(nums)): # 遍历第二个数的下标（只需从i+1开始，避免和自身重复） for j in range(i + 1, len(nums)): # 判断两数之和是否等于目标值 if nums[i] + nums[j] == target: return [i, j] # 返回下标对 return [] # 如果没有找到，返回空列表思路 1：复杂度分析时间复杂度：O(n2)O(n^2)O(n2)，其中 nnn 为数组 numsnumsnums 的元素数量。空间复杂度：O(1)O(1)O(1)。3.2 统计平方和三元组的数目3.2.1 题目链接1925. 统计平方和三元组的数目 - 力扣（LeetCode）3.2.2 题目大意描述：给你一个整数 nnn。 要求：请你返回满足 1≤a,b,c≤n1 \le a, b, c \le n1≤a,b,c≤n 的平方和三元组的数目。 说明： 平方和三元组：指的是满足 a2+b2=c2a^2 + b^2 = c^2a2+b2=c2 的整数三元组 (a,b,c)(a, b, c)(a,b,c)。1≤n≤2501 \le n \le 2501≤n≤250。示例： 示例 1：输入 n = 5 输出 2 解释 平方和三元组为 (3,4,5) 和 (4,3,5)。示例 2：输入：n = 10 输出：4 解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10)。3.2.3 解题思路思路 1：枚举算法直接枚举 aaa 和 bbb，计算 c2=a2+b2c^2 = a^2 + b^2c2=a2+b2，判断 ccc 是否为整数且 1≤c≤n1 \leq c \leq n1≤c≤n，如果满足条件则计数加一，最后返回总数。 该方法时间复杂度为 O(n2)O(n^2)O(n2)。 注意：为避免浮点误差，可以用 a2+b2+1\sqrt{a^2 + b^2 + 1}a2+b2+1 代替 a2+b2\sqrt{a^2 + b^2}a2+b2，这样判断 ccc 是否为整数更安全。思路 1：代码class Solution: def countTriples(self, n: int) -> int: cnt = 0 # 统计满足条件的三元组个数 for a in range(1, n + 1): # 枚举 a for b in range(1, n + 1): # 枚举 b # 计算 c，注意加 1 防止浮点误差 c = int(sqrt(a * a + b * b + 1)) # 判断 c 是否在范围内，且 a^2 + b^2 == c^2 if c <= n and a * a + b * b == c * c: cnt += 1 # 满足条件，计数加一 return cnt # 返回最终统计结果思路 1：复杂度分析时间复杂度：O(n2)O(n^2)O(n2)。空间复杂度：O(1)O(1)O(1)。4. 总结枚举算法通过遍历所有可能状态来寻找解，优点是实现简单、思路直接、正确性易于验证；缺点是在问题规模增大时时间开销迅速上升，往往无法满足效率要求。 它适用于规模较小、可快速验证答案的问题，或作为基线方案、结果校验与对拍工具。实战中应尽量结合剪枝（添加约束、提前判定不可能）、缩小搜索空间（利用对称性、边界与不变量）、降维与变量替换、以及避免重复计算等手段，显著提升效率。 实践建议是：先写出「能过的暴力正确解」，再围绕「减分支、减范围、减重算」迭代优化；当复杂度仍难以接受时，考虑切换到更合适的范式，例如哈希加速、双指针与滑动窗口、二分查找、分治、动态规划或图算法等。 练习题目0001. 两数之和 0204. 计数质数 1925. 统计平方和三元组的数目 2427. 公因子的数目 LCR 180. 文件组合 2249. 统计圆内格点数目 枚举算法题目列表