D7000和D300s的定位分别是什么？# PhotoGear - 摄影器材
C*4
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)。
本文转载至"青云算法"微信公众号，欢迎大家一起来探讨更多解题。
和为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)。
本文转载至"青云算法"微信公众号，欢迎大家一起来探讨更多解题。
