今天看了《剑指offer》里的这道题，发现如果利用好等差数列的性质，其实可以有更好的解法！

题意

比如，s=15，那么应该输出以下三个序列：

7 + 8 = 15 4 + 5 + 6 = 15 1 + 2 + 3 + 4 + 5 = 15

剑指offer的解法

从1开始，枚举序列的第一个数字，然后顺序递增，直到找到或超过了s。 比如s=9，那么搜索过程是： start=1, end=2, 1+2=3 < 9 start=1, end=3, 1+2+3=6 < 9 start=1, end=4, 1+2+3+4=10 > 9，跳过1

start=2, end=3, 2+3=5 < 9， start=2, end=4, 2+3+4 = 9（get），跳过2

start=3, end=4, 3+4=7 < 9， start=3, end=5, 3+4+5=12 > 9，跳过3

start=4, end=5, 4+5=9（get，终止了，因为两个数字的和为9是极致了）

这样的算法的时间复杂度是多少呢？ 由等差数列的求和公式 sum=(n)(n+1)2 可知，每次枚举start的时候，最多需要 O(sum∗2−−−−−−√) 次，而最多有 sum∗2−−−−−−√ 个start（序列里数字的个数从2到根号2*sum，start的个数与序列里数字的个数一一对应，由此知道最多需要枚举多少个start），那么总的复杂度就是 O(sum) 。

线性的，其实已经挺不错的了。

我的解法

假设序列里有k个数字，要求的和为s。

观察等差数列： 1, 2, 3, 4 其中1 + 4 = 2 + 3 = 5，我们知道，里面对称的两个数字的和必定都相等，那么就是s / (k/2) = sumOfMiddle，其中sumOfMiddle就是这些两两加起来的和，在这里是5。从sumOfMiddle知道最中间的靠左的数字必定是middleLeft = (sumOfMiddle-1)/2，它是第k/2个数字，由此可以推知序列的第一个数字为：start = middleLeft - k/2 + 1。

再看奇数个数的序列： 1, 2, 3, 4, 5 其中1 + 5 = 2 + 4 = 3 * 2，类似地，有s / k = middle，其中middle在这里就是3，就是最中间的这个数字，最中间的数字是序列里的第(k+1)/2个数字，所以序列的第一个数字为：start = middle - (k+1)/2 + 1 = middle - (k-1)/2。

有了上面的分析，写起代码也很简单了：

#include <stdio.h> #include <math.h> // 是否为奇数 inline bool isOdd(int n) { return (n & 1) != 0; } // 是否为偶数 inline bool isEven(int n) { return (n & 1) == 0; } // 输出符合条件的正整数连续序列 void print(int start, int key) { int sum = 0; for (int i = start; sum < key; ++i) { sum += i; printf("%d %c ", i, (sum == key) ? '=' : '+'); } printf("%d\n", key); } // 计算符合条件的序列的核心，根据等差数列的性质 void cal(int key) { int maxNum = sqrt(key << 1); for (int i = 2; i <= maxNum; ++i) { int half = i >> 1; if (isOdd(i) && key % i == 0) { int start = key / i - half; if (start > 0) print(start, key); } else if (isEven(i) && key % half == 0) { int sumOfMiddle = key / half, start = ((sumOfMiddle-1) >> 1) - half + 1; if (isOdd(sumOfMiddle) && start > 0) print(start, key); } } } int main() { cal(15); printf("\n"); cal(9); printf("\n"); cal(100); printf("\n"); return 0; }

那么，不禁问一下，时间复杂度是几许？

代码里只有一重循环，遍历的是序列里可能的数字个数，判断是否满足条件的时间是O(1)，所以整个算法的时间复杂度为 O(sum∗2−−−−−−√) ，是不是比上面的好一点呢？

ps，如果考虑计算机的ALU做除法和取模很慢的话，那么第一种解法确实是比较实惠的，具体得真机测试才知道孰好孰坏～