下面给大家分享的是和为S的连续正数序列的代码实现和思路，应该如何用代码来实现呢?下面一起来了解一下。

题目：

做了一道数学题，要求计算出9~16的和，我马上得出正确答案是100，可是，我并不满足与此，我在想，究竟还有多少这样的连续的正数序列的和为100(至少包括两个数)?

之后，我得到了另外一组连续正数和为100的序列:18,19,20,21,22。

问题交给你，你是都也可以迅速的找出所有和为S的连续正数序列呢?

输出描述：输出所有和为S的连续正数序列。

序列内依照从小到大的顺序，序列间依照开始数字从小至大的顺序。

思路1：

双指针技术，相当于有一个窗口，窗口的左右两边就是两个指针，我们根据窗口内值之和来确定窗口的位置和宽度。

代码实现：

import java.util.ArrayList;
public class Solution
{
    public ArrayList < ArrayList < Integer > > FindContinuousSequence(int sum)
    {
        //存放结果
        ArrayList < ArrayList < Integer > > result = new ArrayList < > ();
        //两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
        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);
                }
                result.add(list);
                plow++;
                //如果当前窗口内的值之和小于sum，那么右边窗口右移一下
            }
            else if (cur < sum)
            {
                phigh++;
            }
            else
            {
                //如果当前窗口内的值之和大于sum，那么左边窗口右移一下
                plow++;
            }
        }
        return result;
    }
}

思路2：

双指针问题，在总和小于sum，大指针继续+，否则小指针+

代码实现：

class Solution
{
    public:
        vector < vector < int > > FindContinuousSequence(int sum)
        {
            vector < vector < int > > allRes;
            int phigh = 2, plow = 1;
            while (phigh > plow)
            {
                int cur = (phigh + plow) * (phigh - plow + 1) / 2;
                if (cur < sum)
                    phigh++;
                if (cur == sum)
                {
                    vector < int > res;
                    for (int i = plow; i <= phigh; i++)
                        res.push_back(i);
                    allRes.push_back(res);
                    plow++;
                }
                if (cur > sum)
                    plow++;
            }
            return allRes;
        }
};

思路3：

依据数学公式计算:(a1+an)*n/2=s n=an-a1+1

(an+a1)*(an-a1+1)=2*s=k*l(k>l)

an=(k+l-1)/2 a1=(k-l+1)/2

代码实现：

import java.util.ArrayList;
public class Solution
{
    public ArrayList < ArrayList < Integer > > FindContinuousSequence(int sum)
    {
        ArrayList < ArrayList < Integer >> list = new ArrayList < ArrayList < Integer >> ();
        if (sum < 3) return list;
        int s = (int) Math.sqrt(2 * sum);
        for (int i = s; i >= 2; i--)
        {
            if (2 * sum % i == 0)
            {
                int d = 2 * sum / i;
                if (d % 2 == 0 && i % 2 != 0 || d % 2 != 0 && i % 2 == 0)
                {
                    int a1 = (d - i + 1) / 2;
                    int an = (d + i - 1) / 2;
                    ArrayList < Integer > temp = new ArrayList < Integer > ();
                    for (int j = a1; j <= an; j++)
                        temp.add(j);
                    list.add(temp);
                }
            }
        }
        return list;
    }
}

更多Java实例，请继续关注本站了解吧。更多的内容可以分享给大家。