每日算法系列【LeetCode 829】连续整数求和

简介: 每日算法系列【LeetCode 829】连续整数求和

题目描述

给定一个正整数 N ,试求有多少组连续正整数满足所有数字之和为 N ?

示例1

输入:
5
输出:
2
解释:
5 = 5 = 2 + 3,共有两组连续整数([5],[2,3])求和后为 5。

示例2

输入:
9
输出:
3
解释:
9 = 9 = 4 + 5 = 2 + 3 + 4

示例3

输入:
15
输出:
4
解释:
15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示

  • 1 <= N <= 10^9

题解

这是一道非常经典的数学题,挺基础的,不知道为什么这也能算困难难度的题目?

暴力法

遍历所有的连续数字区间 (i, j) ,然后求和看等不等于 N 。这种方法时间复杂度是  ,显然不可行。

暴力法优化

遍历所有的连续数字区间的左端点 i。然后假设区间长度为 n ,那么根据求和公式有 (2i+n-1)n/2=N ,然后只需要看这个方程的解是否是整数就行。时间复杂度可以降到  ,但还是太高了。

数学方法

根据上面的求和公式,对于起点 i 和长度 n ,求和得到 (2i+n-1)n/2=N 。我们可以先粗略推算一下 i 和 n 的范围,起点 i 的范围是 [1, N]毋庸置疑,而区间长度 n 的范围就可以考究一下了,一个出发点是:上面式子可以解出 i=(N-n(n-1)/2)/n ,而 i>=1 ,可以解出 (n+1)n<=2N ,所以 n 的范围其实只有根号 N 级别,可以直接遍历。另一个出发点是最小的 n 个数加起来就是 1 加到 n 等于 n(n+1)/2 ,这个要小于等于 N ,解出来也是 (n+1)n<=2N 。

所以我们只需要从 1 开始遍历 n ,直到 (n+1)n>2N 为止,然后判断 (N-n(n-1)/2)/n 是否是整数就行了(前面终止条件可以保证 i 一定大于 0 )。

最终时间复杂度降到了  。

代码

数学方法(c++)

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int res = 0;
        for (int n = 1; (n + 1) * n <= 2 * N; ++n) {
            if ((N - n * (n - 1) / 2) % n == 0) res++;
        }
        return res;
    }
};

数学方法(python)

class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        res = 0
        for n in range(1, N+1):
            if n * (n + 1) > 2 * N:
                break
            if (N - n * (n - 1) // 2) % n == 0:
                res += 1
        return res

后记

这题还可以用质因数分解等方法进一步优化,但是没有必要。

相关文章
|
2月前
|
存储
LeetCode整数反转
解决LeetCode上的整数反转问题的几种方法,包括错误的方法和优化后的解决方案,以及如何避免反转后的整数超出32位有符号整数范围的问题。
35 1
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
41 0
|
25天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
29 2
|
2月前
【LeetCode】整数翻转
【LeetCode】整数翻转
16 1
|
2月前
|
存储 C++
Leetcode第十二题(整数转罗马数字)
LeetCode第12题“整数转罗马数字”的解题方法,包括罗马数字的基本规则和特殊规则,以及如何使用C++实现整数到罗马数字的转换。
17 0
|
2月前
|
C++
Leetcode第十三题(罗马数字转整数)
这篇文章介绍了LeetCode第13题“罗马数字转整数”的解题方法,通过一个C++的类`Solution`中的`romanToInt`函数来实现,该函数使用哈希表和遍历字符串的方法,根据罗马数字的规则将输入的罗马数字字符串转换为对应的整数值。
52 0
|
2月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
19 0
|
4月前
|
人工智能 算法
第一周算法设计与分析:C : 200和整数对之间的情缘
这篇文章介绍了解决算法问题"200和整数对之间的情缘"的方法,通过统计数组中每个数模200的余数,并计算每个同余类中数的组合数来找出所有满足条件的整数对(i, j),使得\( A_i - A_j \)是200的整数倍。
|
4月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字