leetcode2562.倍数求和[easy](python)
原创leetcode2562.倍数求和[easy](python)
原创
从不摸鱼的van
发布于 2023-10-17 15:29:29
代码可运行
发布于 2023-10-17 15:29:29
运行总次数：0
代码可运行
本题是2023年10月17日每日一题
问题描述：
给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。
返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。
解题思路一：暴力枚举
首先就想到的是暴力枚举了，直接初始化一个sums=0 ，然后从1开始枚举到n，看每一个数据是否能被3，5，7中的任意一个整除，能就累加到sums。
题解：
class Solution:
def sumOfMultiples(self, n: int) -> int:
sums = 0
for i in range(1,n+1):
if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
sums += i
return sums 
运行时间与内存
这个时候发现运行时间很长。
再小优化一下，让i从3开始遍历，因为小于3的数不可能被整除：
class Solution:
def sumOfMultiples(self, n: int) -> int:
sums = 0
i = 3
while i >= n:
if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
sums += i
i += 1
return sums 
运行时间与内存
思路二：这时尝试一下减少枚举次数，但本质上还是O(n)的算法：
由于求的是1～n的累加和，所以我们直接把从1～n关于3，5，7的倍数加起来，但是要注意去掉重复的最小公倍数，如15，21，等等。
class Solution:
def sumOfMultiples(self, n: int) -> int:
sums = 0
i = 3
while i <= n:
sums += i
i += 3
j = 5
while j <= n:
if j % 3 == 0:
# 重复则去重
j += 5
continue
sums += j
j += 5
k = 7
while k <= n:
if k % 3 == 0 or k % 5 == 0:
# 同上，重复则去重
k += 7
continue
sums += k
k += 7
return sums
运行时间和内存
还有一种数学思路解题，但不涉及编程，所以直接略过。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录