本文讲解如何用数学公式替代暴力循环，将时间复杂度从 o(n) 降至 o(1)，彻底解决 hackerrank 等平台中因循环过深导致的“time limit exceeded”超时问题。
本文讲解如何用数学公式替代暴力循环，将时间复杂度从 o(n) 降至 o(1)，彻底解决 hackerrank 等平台中因循环过深导致的“time limit exceeded”超时问题。
在处理 Project Euler 第 1 题（如 HackerRank 版本：Euler001）时，一个常见误区是使用双重 for 循环遍历所有 3 和 5 的倍数——尤其当输入规模较大（例如 n 接近 10⁹，或测试用例 t 较多）时，该方法会迅速触发超时（TLE）。你提供的代码虽逻辑正确，但本质仍是线性扫描：
// ❌ 低效：时间复杂度 O(n/3 + n/5) ≈ O(n)，对大 n 极慢
for (let x = 0; x < n / 3; x++) total += 3 * x;
for (let x = 0; x < n / 5; x++) {
if (x % 3 !== 0) total += 5 * x; // 去重逻辑也增加开销
}根本解法：利用等差数列求和公式，实现 O(1) 计算
所有小于 n 的 k 的倍数构成等差数列：k, 2k, 3k, ..., mk，其中最大项 mk
该数列和为：
[
S_k = k \cdot (1 + 2 + \cdots + m) = k \cdot \frac{m(m+1)}{2}
]
因此，所求答案为：
[
\text{sum}(3) + \text{sum}(5) - \text{sum}(15)
]
（减去 sum(15) 是因为 15 是 3 和 5 的最小公倍数，其倍数被重复计算了两次）
以下是优化后的完整 JavaScript 实现（兼容 HackerRank 输入格式）：
function sumOfMultiples(k, n) {
const m = Math.floor((n - 1) / k); // 小于 n 的最大倍数索引
return k * m * (m + 1) / 2;
}
function main() {
const t = parseInt(readLine());
for (let i = 0; i < t; i++) {
const n = parseInt(readLine());
const result =
sumOfMultiples(3, n) +
sumOfMultiples(5, n) -
sumOfMultiples(15, n);
console.log(result);
}
}✅ 优势说明：
- 每组输入仅执行常数次算术运算（除法、乘法、加减），无论 n 是 10³ 还是 10⁹，耗时几乎不变；
- 完全规避循环，无重复判断、无条件分支开销；
- 数学推导严谨，结果 100% 准确（整数运算中 /2 因 m(m+1) 必为偶数，结果恒为整数）。
⚠️ 注意事项：
- 使用 Math.floor((n-1)/k) 而非 n/k，确保只统计 严格小于 n 的倍数（题目明确要求 “below n”）；
- 若语言环境不保证整数除法精度（如早期 JS），建议显式使用 Math.floor；
- 此方法可轻松扩展至多个因子（如 3/5/7），只需用容斥原理增减对应 LCM 项。
通过将算法从「模拟过程」升维到「数学建模」，你不仅解决了超时问题，更掌握了处理大规模枚举类题目的核心范式：优先寻找闭式解，而非优化循环。
