Easy

题目描述

给你一个正整数 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 <= 1000

解题思路

这道题有两种主要解法：

方法一：直接遍历（推荐）

最直观的解法是遍历 [1, n] 范围内的所有数字，检查每个数字是否能被 3、5 或 7 整除。如果能被其中任何一个数整除，就将其加入结果。

由于 n ≤ 1000，时间复杂度 O(n) 完全可以接受，代码简洁易懂。

方法二：容斥原理

利用容斥原理计算能被 3、5、7 整除的数的和：

  • 先分别计算能被 3、5、7 整除的数的和
  • 减去能被 3∩5、3∩7、5∩7 整除的数的和（避免重复计算）
  • 加上能被 3∩5∩7 整除的数的和（因为被减了两次）

对于能被 k 整除的数的和，可以用等差数列求和公式：sum = k * count * (count + 1) / 2，其中 count = n / k。

虽然容斥原理在理论上更优雅，但对于这道题的数据规模，直接遍历更简单实用。

代码实现

class Solution {
public:
    int sumOfMultiples(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }
};

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        return sum(i for i in range(1, n + 1) if i % 3 == 0 or i % 5 == 0 or i % 7 == 0)

public class Solution {
    public int SumOfMultiples(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var sumOfMultiples = function(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        if (i % 3 === 0 || i % 5 === 0 || i % 7 === 0) {
            sum += i;
        }
    }
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型直接遍历容斥原理
时间复杂度O(n)O(1)
空间复杂度O(1)O(1)