倍数求和

难度:

标签:

题目描述

Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, or 7.

Return an integer denoting the sum of all numbers in the given range satisfying the constraint.

Example 1:

Input: n = 7
Output: 21
Explanation: Numbers in the range [1, 7] that are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21.

Example 2:

Input: n = 10
Output: 40
Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum of these numbers is 40.

Example 3:

Input: n = 9
Output: 30
Explanation: Numbers in the range [1, 9] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of these numbers is 30.

Constraints:

1 <= n <= 10³

代码结果

运行时间: 26 ms, 内存: 16.0 MB

/*
 * 思路：
 * 使用 Java Stream API 来简化代码。
 * 利用 IntStream.rangeClosed 生成 1 到 n 的数字流，
 * 然后使用 filter 过滤能被 3、5、7 整除的数字，
 * 最后使用 sum 汇总结果。
 */
import java.util.stream.IntStream;
public class Solution {
    public int sumOfDivisibles(int n) {
        return IntStream.rangeClosed(1, n)
                        .filter(i -> i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
                        .sum();
    }
}

解释

方法:

该题解使用了容斥原理。首先计算1到n之间能被3、5、7分别整除的数字之和，然后减去能同时被3和5、3和7、5和7整除的数字之和，最后加上能同时被3、5和7整除的数字之和。对于每个因子，使用等差数列求和公式计算能被该因子整除的数字之和。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆

在使用容斥原理处理这个问题时，你是如何确定同时被3、5、7整除的数字之和需要加回来的？

▷

在使用容斥原理时，我们首先计算了被单个数（如3、5、7）整除的数字之和，但这样会重复计算那些同时被多个数整除的数字（例如同时被3和5整除的数字）。因此，我们接着减去这些重复计算的部分（例如被15整除的数字之和）。但在减去这些重复部分后，那些同时被三个数整除的数字（例如105）会被重复减掉三次，所以需要加回一次，以确保计算的正确性。这就是为什么需要将同时被3、5和7整除的数字之和加回来的原因。

🦆

为什么在计算能被多个数同时整除的数字时，需要使用负号（如(15, -1)）？

▷

这是因为在计算被单个数字整除的数字之和时，一些数字被多次计算。例如，15是3和5的公倍数，因此在计算被3整除的数字和被5整除的数字时，被15整除的数字被重复计算了。为了从总和中去除这种重复，我们使用负号来减去这些数字的和。类似地，对于其他的公倍数如21（3和7的公倍数）和35（5和7的公倍数），同样需要使用负号减去它们的和。

🦆

在计算能被单个数字整除的数字之和时，为什么选择使用等差数列求和公式？

▷

当我们计算能被某个数字k整除的所有数字之和时，这些数字实际上形成了一个等差数列，其中首项是k，公差也是k。使用等差数列求和公式可以有效地计算这种序列的总和，公式是：首项加末项乘以项数除以2。在这种情况下，末项是n内最大的能被k整除的数，项数是n除以k。这种方法比依次添加每个数字更高效。

🦆

列表推导式中的(n // num) * (n // num + 1) * num * sign // 2是如何推导出来的？

▷

这个表达式来源于等差数列求和公式。首先，(n // num)是等差数列中的项数，即n以内能被num整除的数字的个数。num是等差数列的首项和公差，所以末项是num乘以(n // num)。等差数列求和公式是首项加末项乘以项数除以2，这里首项是num，末项是num乘以(n // num)，项数是(n // num)。将这些值代入公式，得到(n // num) * (n // num + 1) * num // 2。sign变量用于根据容斥原理进行加减调整。

倍数求和

题目描述

代码结果

解释

代码细节讲解

相关问题