《编程之美》 2.21只考虑加法

我们知道:

1+2 = 3；

4+5 = 9；

2+3+4 = 9。

等式的左边都是两个或两个以上连续的自然数相加，是不是所有的整数都可以写成这样的形式呢？

问题1：  对于一个64位正整数，输出它所有可能的连续自然数（两个以上）之和的算式。

问题2：  大家在测试上面程序的过程中，肯定会注意到有一些数字不能表达为一系列连续的自然数

之和，例如32好像就找不到。那么，这样的数字有什么规律呢？能否证明你的结论？

问题3： 在64位正整数范围内，子序列数目最多的数是哪一个？

问题一解法：双指针遍历

这题有两种解法， 其中一种便是双指针法，还有一种比较巧妙，利用了数学方法，简单来说是求出一个公式来。这里只说双指针的解法。

这里需要一个转化，把求n中所有可能的连续自然数之和归约为在数组{1,2,3,...,n}中找所有连续子序列和等于n的问题。这里同样也是这样一个场景：对有序数组如何遍历来求得符合要求的数据集合？这时的双指针可以不是一头一尾了，而是两个都指向头部，这样可以以高效的顺序遍历我们要找的所有集合。初始设i=j=1，这里同样会出现三种情况：

这样，代码就出来了：

public static void GetAnswer(int n)        {            int i =0, j = 0;            while (i <= (n / 2) && j <= n)            {                int sum = (j + i)*(j - i + 1) / 2;                if (sum == n)                {                    for (int k = i; k <= j; k++)                    Console.WriteLine(k);                    i++;                    j++;                }                else if (sum < n) //sum[i..j]<n,只能提高j以增大sum                {                    j++;                }                                    else //sum[i..j]>n,只能提高i以减小sum                {                    i ++;                }            }        }所谓双指针，是利用两个指针对一个有序数组进行遍历，查找出符合要求的数据集合。相信大家都接触到了这种思维模式的解题方法，只是没有注意到罢了。