力扣热题——分类求和并作差

目录

题目链接：2894. 分类求和并作差 - 力扣（LeetCode）

题目描述

解法一：遍历求解

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

解法二：数学优化法

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

---

题目链接：2894. 分类求和并作差 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你两个正整数 n 和 m 。

现定义两个整数 num1 和 num2 ，如下所示：

• 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

---

解法一：遍历求解

        常规遍历解法的核心就是通过循环遍历区间内的所有整数，根据是否能被 m 整除进行分类累加。具体步骤如下：

1. ​​初始化累加器​​：定义两个变量 num1 和 num2，分别用于累加无法被 m 整除和能够被 m 整除的整数之和。
2. ​​循环遍历​​：对区间 [1, n] 内的每个整数 i 进行遍历，利用条件判断 i % m != 0 将数值分类累加到 num1 或 num2 中。
3. ​​结果计算​​：最终返回 num1 - num2 的差值。

        这个方法的优势就在于逻辑比较直观，非常易于实现，不过时间复杂度为 O(n)，当 n 较大时效率较低。

Java写法：

public class Solution {public int differenceOfSums(int n, int m) {int num1 = 0, num2 = 0;for (int i = 1; i <= n; i++) {if (i % m != 0) num1 += i;else num2 += i;}return num1 - num2;}
}

C++写法：

class Solution {
public:int differenceOfSums(int n, int m) {int num1 = 0, num2 = 0;for (int i = 1; i <= n; i++) {(i % m != 0) ? num1 += i : num2 += i;}return num1 - num2;}
};

运行时间

时间复杂度和空间复杂度

​​方法​​	​​时间复杂度​​	​​适用场景​​	​​核心思想​​
常规遍历法	O(n)	小规模数据或调试	条件判断与累加
数学优化法	O(1)	大规模数据或高效计算	等差数列求和与整体映射关系

---

---

---

解法二：数学优化法

数学优化解法就是通过公式直接计算结果，避免了遍历操作。其核心步骤如下：

1. ​​总和计算​​：区间 [1, n] 所有整数之和为 S = n*(n+1)/2。
2. ​​可被 m 整除的数列​​：这些数构成等差数列 m, 2m, 3m, ..., km（其中 k = n/m 取整），其和为 num2 = m * k*(k+1)/2。
3. ​​结果公式推导​​：无法被 m 整除的数和为 S - num2，因此所求差值为 (S - num2) - num2 = S - 2*num2。

        这个方法的时间复杂度为 O(1)，效率远远高于常规遍历法，尤其适用于大范围数据。

Java写法：

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

C++写法：

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

运行时间

时间复杂度和空间复杂度

​​方法​​	​​时间复杂度​​	​​适用场景​​	​​核心思想​​
常规遍历法	O(n)	小规模数据或调试	条件判断与累加
数学优化法	O(1)	大规模数据或高效计算	等差数列求和与整体映射关系

---

总结

        本文介绍了两种计算区间[1,n]内整数基于能否被m整除的分类差值方法。常规遍历法通过循环判断累加，时间复杂度O(n)，易于实现但效率较低。数学优化法则利用等差数列求和公式直接计算结果，时间复杂度降至O(1)，特别适合大规模数据处理。两种方法分别适用于不同场景：遍历法适合小规模数据调试，数学方法更适合高效计算需求。两种解法均提供了Java和C++的实现代码示例。