枚举:优化范围
约 10 分钟
枚举就是把所有可能一个个试。能不能不超时,往往取决于范围定得准不准——范围缩小一半,时间就省一半。
以"找两个正整数之和为 "为例,第一个数 没必要枚举到 。因为两数为正且不重复地取 ,所以 最大只到 ,超过就重复了:
for (int a = 1; a <= n / 2; a++) {
int b = n - a; // 第二个数直接算出来
// 处理 (a, b)
}
这里还顺手用了个技巧:定了 , 就唯一确定,根本不用第二层循环。
优化范围的通用思路:先想清楚每个变量的取值必须满足什么条件(正数、有上界、不重复),把这些写进循环的起止和步长。 和 看着只差常数,但在大数据和多重循环里,常数叠起来就是超时和通过的区别。读题时一定要挖出这些隐含范围。
小纸条
找两个数之和为 n,第一个数最大枚举到多少?
登录 后可看答案