Easy

题目描述

给你正整数 n 和 m。

定义两个整数如下：

  • num1：范围 [1, n]（两端都包含）内所有不能被 m 整除的整数的和。
  • num2：范围 [1, n]（两端都包含）内所有能被 m 整除的整数的和。

返回整数 num1 - num2。

示例 1：

输入：n = 10, m = 3
输出：19
解释：在给定示例中：
- 范围 [1, 10] 内不能被 3 整除的整数为 [1,2,4,5,7,8,10]，num1 是这些整数的和 = 37。
- 范围 [1, 10] 内能被 3 整除的整数为 [3,6,9]，num2 是这些整数的和 = 18。
我们返回 37 - 18 = 19 作为答案。

示例 2：

输入：n = 5, m = 6
输出：15
解释：在给定示例中：
- 范围 [1, 5] 内不能被 6 整除的整数为 [1,2,3,4,5]，num1 是这些整数的和 = 15。
- 范围 [1, 5] 内能被 6 整除的整数为 []，num2 是这些整数的和 = 0。
我们返回 15 - 0 = 15 作为答案。

示例 3：

输入：n = 5, m = 1
输出：-15
解释：在给定示例中：
- 范围 [1, 5] 内不能被 1 整除的整数为 []，num1 是这些整数的和 = 0。
- 范围 [1, 5] 内能被 1 整除的整数为 [1,2,3,4,5]，num2 是这些整数的和 = 15。
我们返回 0 - 15 = -15 作为答案。

约束：

  • 1 <= n, m <= 1000

提示：

  • 根据等差数列，我们知道范围 [1, n] 内整数的和为 n * (n + 1) / 2。

解题思路

这道题有两种主要解法：

方法一：数学公式法（推荐） 关键观察：num1 + num2 = 1到n的所有数字之和 = n*(n+1)/2。因此 num1 - num2 = (num1 + num2) - 2num2 = n(n+1)/2 - 2*num2。

计算num2（能被m整除的数字之和）：

  • 在[1,n]范围内，能被m整除的数字为：m, 2m, 3m, …, km，其中k = n/m
  • 这是首项为m，公差为m的等差数列，项数为k
  • 和为：m * (1 + 2 + … + k) = m * k * (k + 1) / 2

方法二：暴力遍历法 直接遍历[1,n]范围内的所有数字，根据是否能被m整除分别累加到num1或num2中。时间复杂度O(n)，但代码更直观。

数学公式法的时间复杂度为O(1)，更加高效，是最优解。

代码实现

class Solution {
public:
    int differenceOfSums(int n, int m) {
        int totalSum = n * (n + 1) / 2;
        int k = n / m;
        int num2 = m * k * (k + 1) / 2;
        return totalSum - 2 * num2;
    }
};

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        total_sum = n * (n + 1) // 2
        k = n // m
        num2 = m * k * (k + 1) // 2
        return total_sum - 2 * num2

public class Solution {
    public int DifferenceOfSums(int n, int m) {
        int totalSum = n * (n + 1) / 2;
        int k = n / m;
        int num2 = m * k * (k + 1) / 2;
        return totalSum - 2 * num2;
    }
}

var differenceOfSums = function(n, m) {
    const totalSum = Math.floor(n * (n + 1) / 2);
    const k = Math.floor(n / m);
    const num2 = Math.floor(m * k * (k + 1) / 2);
    return totalSum - 2 * num2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数学公式法暴力遍历法
时间复杂度O(1)O(n)
空间复杂度O(1)O(1)