题目描述：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述：输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
问题分析：
（1）题目要求的是和为sum的公差为一的等差数列，由等差数列的求和公式可知，S=（a1+an）*n/2 ，a1越小，n越大，当a1=1时，an=n，所以n<√2S。所以遍历从2到√2S之间的数，当n为奇数时，判断序列的中间值是否为序列平均值： sum % n == 0；当n为偶数时，判断序列中间两个数的平均值是否为序列的平均值：(sum % n) * 2 == n。符合要求则将序列添加到结果。
（2）看到另一个巧妙的思路是利用滑动窗口，也叫双指针技术，从初始的两个数1和2开始，分别用两个指针left、right指向这两个数，从left到right之间的数便成为一个窗口。计算窗口中的数的和，如果比sum小则把right向右移；比sum大则把left向右移；如果等于sum，则把窗口中的序列添加到结果中，并把left和right均向右移动。当left=right时，也就意味着不再存在符合条件的序列。代码截图：
网友评论