本文最后更新于 354 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
给你一个正整数 n
,请你计算在 [1,n]
范围内能被 3
、5
、7
整除的所有整数之和。
返回一个整数,用于表示给定范围内所有满足约束条件的数字之和。
示例 1:
输入:n = 7
输出:21
解释:在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21 。
示例 2:
输入:n = 10
输出:40
解释:在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40 。
示例 3:
输入:n = 9
输出:30
解释:在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30 。
提示:
1 <= n <= 10^3
解法一:枚举
算法思路:
枚举 [1, n] 范围内的所有整数,记当前枚举的数为 i,如果 i mod 3 = 0
或 i mod 5 = 0
或 i mod 7 = 0
,那么将 i 加到总和 ans。
代码实现:
class Solution {
public int sumOfMultiples(int n) {
int ans = 0;
for(int i = 1; i <= n ;i++){
if(i%3==0 || i%5==0 || i%7==0){
ans+=i;
}
}
return ans;
}
}
复杂度分析:
时间复杂度: O(n)。
空间复杂度: O(1)。
解法二:容斥原理
算法思路:
我们定义函数 f(x)
表示 [1, ..n]
中能被 x
整除的数之和,那么一共有 m = ⌊n/x⌋
个数能被 x
整除,这些数字分别为 x, 2x, 3x, ⋯, mx
,构成一个等差数列,首项为 x
,末项为 mx
,项数为 m
,因此 f(x) = (x + mx) × m / 2
。
根据 容斥原理 ,我们可以得到答案为: $$ f(3)+f(5)+f(7)−f(3×5)−f(3×7)−f(5×7)+f(3×5×7) $$
代码实现:
class Solution {
private int n;
public int sumOfMultiples(int n) {
this.n = n;
return f(3) + f(5) + f(7) - f(3 * 5) - f(3 * 7) - f(5 * 7) + f(3 * 5 * 7);
}
private int f(int x) {
int m = n / x;
return (x + m * x) * m / 2;
}
}
复杂度分析:
时间复杂度: O(1)。
空间复杂度: O(1)。