分类求和并作差

难度:

标签:

题目描述

You are given positive integers n and m.

Define two integers, num1 and num2, as follows:

num1: The sum of all integers in the range [1, n] that are not divisible by m.
num2: The sum of all integers in the range [1, n] that are divisible by m.

Return the integer num1 - num2.

Example 1:

Input: n = 10, m = 3
Output: 19
Explanation: In the given example:
- Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
- Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18.
We return 37 - 18 = 19 as the answer.

Example 2:

Input: n = 5, m = 6
Output: 15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
- Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0.
We return 15 - 0 = 15 as the answer.

Example 3:

Input: n = 5, m = 1
Output: -15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0.
- Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15.
We return 0 - 15 = -15 as the answer.

Constraints:

1 <= n, m <= 1000

代码结果

运行时间: 22 ms, 内存: 16.0 MB

/*
 * Problem: Given two positive integers n and m, define two integers num1 and num2 as follows:
 * num1: The sum of all integers in the range [1, n] that are not divisible by m.
 * num2: The sum of all integers in the range [1, n] that are divisible by m.
 * Return the integer num1 - num2.
 */
import java.util.stream.IntStream;

public class Solution {
    public int differenceOfSums(int n, int m) {
        int num1 = IntStream.rangeClosed(1, n)
                            .filter(i -> i % m != 0)
                            .sum();
        int num2 = IntStream.rangeClosed(1, n)
                            .filter(i -> i % m == 0)
                            .sum();
        return num1 - num2;
    }
}

解释

方法:

该题解首先计算1到n之间所有整数的总和，这可以通过等差数列求和公式 (1 + n) * n / 2 来完成。接着，作者使用一个循环来求解1到n之间所有能被m整除的整数之和。循环变量cur从m开始，每次增加m，直到超过n为止。每次循环，将cur加到一个累加器diff中。最后，题解返回所有数的总和减去能被m整除的数的总和的两倍，得到的就是所有不能被m整除的数的总和减去能被m整除的数的总和。

时间复杂度:

O(n/m)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么在计算无法被m整除的整数之和时，使用了返回总和减去被m整除的数的总和的两倍的方法？

▷

在这个算法中，首先计算的是1到n所有整数的总和。然后，计算能被m整除的整数之和。如果我们直接从总和中减去能被m整除的整数之和，得到的是不能被m整除的整数之和。但题目要求的是不能被m整除的整数之和减去能被m整除的整数之和，因此需要再减去一次能被m整除的整数之和，即总和减去两倍的能被m整除的数之和。这样处理是为了符合题目的要求，计算出正确的差值。

🦆

在循环中计算能被m整除的数的和时，是否有更高效的算法，比如直接计算而不是逐个累加？

▷

确实有一种更高效的方法来计算能被m整除的数的和，而不需要逐个累加。可以使用等差数列的求和公式来直接计算。设k是n除以m的商（即n/m的整数部分），则能被m整除的数是m, 2m, 3m, ..., km。这是一个首项为m，公差也为m，项数为k的等差数列。等差数列求和公式是（首项 + 末项）* 项数 / 2，所以和为（m + km）* k / 2。这种方法只需进行常数次计算，比循环累加每个能被m整除的数要效率更高。

🦆

如何处理当 m 大于 n 的情况，即没有任何一个数能被 m 整除的特殊情况？

▷

当m大于n时，范围[1, n]内没有任何一个数能被m整除，因此能被m整除的整数之和为0。在这种情况下，num2（能被m整除的数的和）为0。因此，num1（无法被m整除的整数之和）就等于1到n的总和，即用等差数列求和公式(1 + n) * n / 2计算。最后，返回的结果就是num1 - num2，即num1 - 0 = num1。这意味着在m大于n的情况下，直接返回1到n的总和即可。

分类求和并作差

题目描述

代码结果

解释

代码细节讲解

相关问题