解题思路
要求n以内所有3或5的倍数之和，我们可以：
分别计算3的倍数之和和5的倍数之和
减去重复计算的15的倍数之和（因为这些数被计算了两次）
关键点
使用等差数列求和公式加速计算
注意避免重复计算3和5的公倍数
注意计算最大倍数时向下取整
代码
cpp
java
python
#include
using namespace std;
class Solution {
public:
int sumOfMultiples(int n) {
// 将n减1，因为我们要求小于n的数
n--;
// 计算3的倍数之和
int count3 = n / 3;
int sum3 = 3 * (count3 * (count3 + 1)) / 2;
// 计算5的倍数之和
int count5 = n / 5;
int sum5 = 5 * (count5 * (count5 + 1)) / 2;
// 计算15的倍数之和（被重复计算的部分）
int count15 = n / 15;
int sum15 = 15 * (count15 * (count15 + 1)) / 2;
// 返回总和
return sum3 + sum5 - sum15;
}
};
int main() {
int n;
cin >> n;
Solution solution;
cout << solution.sumOfMultiples(n) << endl;
return 0;
}
import java.util.Scanner;
public class Main {
static class Solution {
public int sumOfMultiples(int n) {
// 将n减1，因为我们要求小于n的数
n--;
// 计算3的倍数之和
int count3 = n / 3;
int sum3 = 3 * (count3 * (count3 + 1)) / 2;
// 计算5的倍数之和
int count5 = n / 5;
int sum5 = 5 * (count5 * (count5 + 1)) / 2;
// 计算15的倍数之和（被重复计算的部分）
int count15 = n / 15;
int sum15 = 15 * (count15 * (count15 + 1)) / 2;
// 返回总和
return sum3 + sum5 - sum15;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Solution solution = new Solution();
System.out.println(solution.sumOfMultiples(n));
sc.close();
}
}
class Solution:
def sum_of_multiples(self, n: int) -> int:
# 将n减1，因为我们要求小于n的数
n -= 1
# 计算3的倍数之和
count3 = n // 3
sum3 = 3 * (count3 * (count3 + 1)) // 2
# 计算5的倍数之和
count5 = n // 5
sum5 = 5 * (count5 * (count5 + 1)) // 2
# 计算15的倍数之和（被重复计算的部分）
count15 = n // 15
sum15 = 15 * (count15 * (count15 + 1)) // 2
# 返回总和
return sum3 + sum5 - sum15
def main():
n = int(input())
solution = Solution()
print(solution.sum_of_multiples(n))
if __name__ == "__main__":
main()
算法及复杂度
算法：等差数列求和
时间复杂度：，使用公式直接计算
空间复杂度：，只使用常数额外空间