前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日算法系列【LeetCode 829】连续整数求和

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

作者头像
godweiyang
发布2020-03-24 10:43:38
8580
发布2020-03-24 10:43:38
举报
文章被收录于专栏:算法码上来

题目描述

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

示例1

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

示例2

代码语言:javascript
复制
输入:
9
输出:
3
解释:
9 = 9 = 4 + 5 = 2 + 3 + 4

示例3

代码语言:javascript
复制
输入:
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++)

代码语言:javascript
复制
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)

代码语言:javascript
复制
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

后记

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

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-01-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法码上来 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题解
    • 暴力法
      • 暴力法优化
        • 数学方法
        • 代码
          • 数学方法(c++)
            • 数学方法(python)
            • 后记
            相关产品与服务
            NLP 服务
            NLP 服务(Natural Language Process,NLP)深度整合了腾讯内部的 NLP 技术,提供多项智能文本处理和文本生成能力,包括词法分析、相似词召回、词相似度、句子相似度、文本润色、句子纠错、文本补全、句子生成等。满足各行业的文本智能需求。
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档