C*******4
发帖数: 1 | 1 问题：输入一个整数N，请问有多少种不同的方法把若干个连续的整数相加使得它们的
和为N？例如输入N=9，由于9 = 9、9 = 4 + 5、9 = 2 + 3 + 4，因此正确的输出是3。
分析：这是LeetCode第829题。
解法一：时间复杂度O(n)
我们可以想象有一个整数数组，数组里的第一个数字是1，第二个数字是2，以后的数字
以此类推。再假设有两个指针，第一个指针初始化指向数组的第一个数字，第二个指针
初始化指向数组的第二个数字。这两个指针就定位了一个子数组，该子数组由两个指针
之间的所有数字（包括两个指针指向的数字）组成。由于数组里的数字是连续递增的，
那么两个指针之间的任意子数组的数字也是连续递增的。
如果两个指针之间的子数组的所有数字之和小于输入的整数N，我们希望这个子数组包
含更多的数字，于是把第二个指针向右移动。每把第二个指针向右移动一位，相当于往
子数组的最右边添加一个新的数字，子数组的数字之和也会相应变大。如果此时子数组
的和仍然小于N，我们继续向右移动第二个指针。
如果子数组的和等于N，我们就找到了一个符合条件的子数组。接下来可以继续向右移
动第二个指针去寻找其他符合条件的子数组。
如果子数组的和大于N，我们希望子数组包含更少的数字，于是把第一个指针向右移动
。每把第一个指针向右移动一位，相当删除子数组最左边的数字，子数组的数字之和就
会相应变小。
这就是经典的双指针思路的应用。下面是根据这种思路写出的代码：
public int consecutiveNumbersSum(int N) {
int start = 1;
int end = 2;
int sum = 3;
int count = 1;
while (start <= N / 2) {
if (sum <= N) {
sum += end + 1;
end++;
if (sum == N) {
count++;
}
} else {
sum -= start;
start++;
}
}
return count;
}
在上述代码种，变量start相当于分析中的第一个指针，指向连续数字序列的最小的数
字（子数组的第一个数字）；变量end相当于分析中的第二个指针，指向连续数字序列
的最大的数字（子数组的最有一个数字）。
上述代码中只有一个while循环，循环的每一次执行要么递增变量start，要么递增变量
end。由于start最多递增到N/2，而end最多也不会超过N。因此这种解法的时间复杂度
为O(n)。在LeetCode中，如果输入特别大的数字，比如大于10 ^ 8的数字，有可能超时。
解法二：O(n^0.5)
假设有k个连续的数字，它们的和为N。最小的k个连续的数字之和是1 + 2 + 3 + … +
k。从1开始的连续k个数字之和不一定等于N。可能存在一个整数i，(i + 1) + (i + 2)
+ (i + 3) + … + (i + k) = N。我们把这个等式稍微变换一下就有1 + 2 + 3 + …
+ k + i × k = N，也就是N - (1 + 2 + 3 + … + k) = i × k。
这个公式告诉我们，如果有k个连续的数字的和等于N，那么一定存在一个整数i，N 减
去1 + 2 + 3 + … + k的差等于i × k。也就是说N 减去1 + 2 + 3 + … + k的差一定
能被k整除。
1 + 2 + 3 + … + k的值很容易求出来，用一个从1开始的循环就能做到。下面是各种
思路的参考代码：
public int consecutiveNumbersSum(int N) {
int k = 1;
int sum = 0;
int count = 0;
while (sum < N) {
sum += k;
if (sum <= N && (N - sum) % k == 0) {
count++;
}
k++;
}
return count;
}
最后分析时间复杂度。上述代码中有一个while循环，循环一直执行到1 + 2 + 3 + …
+ k的结果大于N为止。由于1 + 2 + 3 + … + k等于k(k + 1) / 2，那么反过来如果输
入的整数是n，k的值最大也只能是O(n^0.5)，因此第二种解法的时间复杂度是O(n^0.5)。
本文转载至"青云算法"微信公众号，欢迎大家一起来探讨更多解题。 |
d*******n
发帖数: 43 | |
z*********n
发帖数: 1451 | 3 sqrt（n）的解法已经很naive了吧，我以为是贴了更巧妙的解法呢。
给定一个X，如果能被写成连续数字和，那就套下小学的等差数列求和，得出必然存在a
和n使得：
(a + (a + n - 1)) * n / 2 = x
x是给定目标数，已知，任务是求 a 和 n的整数解的个数
那最naive的办法就是用让n取1，2,3,4,... sqrt(2x)，然后拿2X挨个除一下，把所有整
数a给找出来就行了。。。
这比你那个思路简单容易理解多了吧 |
d*******n
发帖数: 43 | 4 金刚兄让我明白了我为什么没拿到Google的offer
在a
有整
【在 z*********n 的大作中提到】
: sqrt（n）的解法已经很naive了吧，我以为是贴了更巧妙的解法呢。
: 给定一个X，如果能被写成连续数字和，那就套下小学的等差数列求和，得出必然存在a
: 和n使得：
: (a + (a + n - 1)) * n / 2 = x
: x是给定目标数，已知，任务是求 a 和 n的整数解的个数
: 那最naive的办法就是用让n取1，2,3,4,... sqrt(2x)，然后拿2X挨个除一下，把所有整
: 数a给找出来就行了。。。
: 这比你那个思路简单容易理解多了吧
|
g****y
发帖数: 2810 | 5 这个题目我比赛错了6次
在a
有整
【在 z*********n 的大作中提到】
: sqrt（n）的解法已经很naive了吧，我以为是贴了更巧妙的解法呢。
: 给定一个X，如果能被写成连续数字和，那就套下小学的等差数列求和，得出必然存在a
: 和n使得：
: (a + (a + n - 1)) * n / 2 = x
: x是给定目标数，已知，任务是求 a 和 n的整数解的个数
: 那最naive的办法就是用让n取1，2,3,4,... sqrt(2x)，然后拿2X挨个除一下，把所有整
: 数a给找出来就行了。。。
: 这比你那个思路简单容易理解多了吧
|
z*********n
发帖数: 1451 | 6 看ls这么一说，怕有啥坑没想到，赶快找到这题写了下，没发现有啥坑直接就pass了，
就按那个等差数列实现下就行了。
class Solution {
public int consecutiveNumbersSum(int target) {
int count = 0, t = 2 * target;
for (int n = 1; n < Math.sqrt(t); ++ n)
if (t % n == 0 && (t / n + 1 - n) % 2 == 0 )
count ++;
return count;
}
} |
z*********n
发帖数: 1451 | 7
大宝建不但题刷的好，还这么谦虚，自叹不如啊。
【在 d*******n 的大作中提到】
: 金刚兄让我明白了我为什么没拿到Google的offer
:
: 在a
: 有整
|
m********u
发帖数: 3942 | |
z*********n
发帖数: 1451 | 9
你们这行也关注刷题么。。。
【在 m********u 的大作中提到】
: 现在都800多题了？？。。。
|
m********u
发帖数: 3942 | 10 哈哈 有时候问问刷到什么程度了。。。没刷好就先别面试了
【在 z*********n 的大作中提到】
:
: 你们这行也关注刷题么。。。
|
