最简单的做法,遍历求和,时间O(n)
class Solution:def sumOfMultiples(self, n: int) -> int:return sum([i if (i % 3 == 0) or (i % 5 == 0) or (i % 7 == 0) else 0 for i in range(n + 1)])
- 如果只求在 [1,n] 内能被m整除的数之和,那么 ans = (m + n // m * m) * (n // m) // 2
- 根据容斥原理,即一共三个事件,被3整除,被5整除,被7整除
- 题中要求这三个事件的交集,也是求三个事件分别独立发生的情况,减去三个事件两两组合发生的情况,最后加上三个事件共同发生的情况
- 时间O(1)
class Solution:def sumOfMultiples(self, n: int) -> int:def f(m: int) -> int:return (m + n // m * m) * (n // m) // 2return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7)