和为指定值的连续序列

输入一个整数s，打印出所有和为s的连续正整数序列（至少包含两个数）。例如，对于输入15，由于有1+2+3+4+5=15，4+5+6=15，7+8=15，所以打印出1~5、4~6、7~8三个序列。

有个比较好的做法是利用等差数列求和公式：s=a*n+n*(n-1)/2。这里的a是第一个元素，n是项数。

int solve(int k)
{int count = 0;for (int i = 1, v = 0; (v = i * (i - 1) / 2) <= k; i++) {if ((k - v) % i == 0) {// a = (k - v) / i;count++;}}return count;
}

 

这种方法只适用于这个特定的应用场景，题目稍微改变一下就不太好处理了。例如，要求求得的序列是某个数值中的连续序列，不再是自然数连续序列，这样就没办法用这个方法了。这种情况下可以先将数组排序，然后按照下面的方法求解即可。

 

int solve(int A[], int N, int val)
{int count = 0, beg = 1, end = 0, sum = A[0];while (beg < end && end < N) {if (sum == val) {count++;// A[beg] -> A[end]sum += A[++end];} else if (sum < val) {sum += A[++end];} else {sum -= A[beg++];}}return count;
}