题解 | #和为S的连续正数序列#

和为S的连续正数序列

http://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe

算法思想一：求和公式

解题思路：

设连续正整数序列的左边界 i 和右边界 j ，则此序列的元素和 tsum 等于元素平均值 (i+j)/2 乘以元素数量 (j−i+1) ，即

$tsum=\frac{(i+j)\times(j-i+1)}{2}$

观察发现，当确定元素和 tsum 与左边界 i 时，可通过解一元二次方程，直接计算出右边界 j ，公式推导如下

$0=j^{2}+j-(2\times tsum + i^{2}-i)$

根据一元二次方程求解：

$j=\frac{-1\pm\sqrt{1+4(2\times tsum+i^{2}-i)}}{2}$

由于j > i 恒成立，可以直接去掉必为负数的解

因此，通过从小到大遍历左边界 i 来计算以 i 为起始数字的连续正整数序列。每轮中，由以上公式计算得到右边界 j ，当 j 满足以下两个条件时记录结果：
j 为整数：符合题目所求「连续正整数序列」；
i<j ：满足题目要求「至少含有两个数」；

代码展示：

Python版本

class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        i, j, res = 1, 2, []
        while i < j:
            j = (-1 + (1 + 4 * (2 * tsum + i * i - i)) ** 0.5) / 2
            if i < j and j == int(j):
                res.append(list(range(i, int(j) + 1)))
            i += 1
        return res

复杂度分析：

时间复杂度 O(N)：其中 N =tsum；连续整数序列至少有两个数字，而 i < j恒成立，因此至多循环 tsum/2 次，使用 O(N)
空间复杂度 O(1)：变量 i, j 使用常数大小的额外空间。

算法思想二：双指针

解题思路：

们用两个指针 plow 和 phigh 表示当前枚举到的以 plow 为起点到 phigh 的区间，cur 表示 [plow, phigh] 的区间和，由求和公式可 O(1) 求得为 cur = (phigh + plow) * (phigh - plow + 1) / 2，起始 plow=1,phigh=2。

一共有三种情况：
    如果 cur<sum 则说明指针 phigh 还可以向右拓展使得 cur 增大，此时指针 phigh向右移动，即 phigh+=1
    如果 cur>sum 则说明以 plow为起点不存在一个 phigh 使得 cur =sum，此时要枚举下一个起点，指针 plow 向右移动，即plow+=1
    如果 cur==sum 则说明我们找到了以 plow 为起点得合法解 [plow, phigh] ，我们需要将 [plow, phigh] 的序列放进答案数组，且我们知道以 plow 为起点的合法解最多只有一个，所以需要枚举下一个起点，指针plow 向右移动，即 plow+=1
终止条件即为 plow > phigh 的时候，这种情况的发生指针 phigh 移动到了 (sum/2)+1 的位置，导致 plow < phigh 的时候区间和始终大于 sum

图解：

代码展示：

JAVA版本

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (sum < 3) {
            return res;
        }
        // 两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
        int plow = 1,phigh = 2;
        while(phigh > plow){
            //由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
            int cur = (phigh + plow) * (phigh - plow + 1) / 2;
            //相等，那么就将窗口范围的所有数添加进结果集
            if(cur == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for(int i=plow;i<=phigh;i++){
                    list.add(i);
                }
                res.add(list);
                plow++;
            //如果当前窗口内的值之和小于sum，那么右边窗口右移一下
            }else if(cur < sum){
                phigh++;
            }else{
            //如果当前窗口内的值之和大于sum，那么左边窗口右移一下
                plow++;
            }
        }
        return res;
    }
}