【每日一题】倍数求和

Tag

【一次遍历】【数组】【2023-10-17】

---

题目来源

2652. 倍数求和

---

题目解读

找出 [1. n] 范围内可以被 3、5、7 整除的所有整数之和。

---

解题思路

方法一：一次遍历

题目简单，思路也很明确，枚举区间 [1, n] 内的所有整数 num：

• num % 3 == 0；
• num % 5 == 0；
• num % 7 == 0；

以上三个条件满足其一，就将 num 加到 sum 中，sum 初始为 0

实现代码

class Solution {
public:
    int sumOfMultiples(int n) {
        int sum = 0;
        for (int num = 1; num <= n; ++num) {
            if (num % 3 == 0 || num % 5 == 0 || num % 7 == 0) {
                sum += num;
            }
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

---

其他语言

c

int sumOfMultiples(int n){
    int sum = 0;
    for (int num = 1; num <= n; ++num) {
        if (num % 3 == 0 || num % 5 == 0 || num % 7 == 0) {
            sum += num;
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9

python3

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

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。