题目主要信息

1、找出所有和为S的连续正数序列?

2、序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

方法一：数学方法

具体方法

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

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

通过从小到大遍历左边界 i 来计算 以 i 为起始数字的连续正整数序列 。

每轮中，由以上公式计算得到右边界 j ，当 j 满足以下两个条件时记录结果： j 为 整数 ：符合题目所求「连续正整数序列」； i<j ：满足题目要求「至少含有两个数」；

Java代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        //使用数学公式
        int i = 1;
        double j = 2.0;
        ArrayList<ArrayList<Integer> > result = new ArrayList<>();
        while(i < j) {
            j = (-1 + Math.sqrt(1 + 4 * (2 * sum + (long) i * i - i))) / 2;
            if(i < j && j == (int)j) {
                ArrayList<Integer> temp = new ArrayList<>();
                for(int k = i; k <= (int)j; k++)
                    temp.add(k);
                result.add(temp);
            }
            i++;
        }
        return result;
    }
}

复杂度分析

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

方法二：滑动窗口

具体方法

设连续正整数序列的左边界 i和右边界 j，则可构建滑动窗口从左向右滑动。循环中，每轮判断滑动窗口内元素和与目标值 target 的大小关系，若相等则记录结果，若大于 target则移动左边界 i（以减小窗口内的元素和），若小于 target则移动右边界 j以增大窗口内的元素和）。

Java代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       //使用滑动窗口
        ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
        int first = 1,second = 1;
        int temp_sum = 0;
        while(first<=sum/2){
            if(temp_sum<sum){
                temp_sum +=second;
                ++second;
            }
            else if(temp_sum>sum){
                temp_sum-=first;
                ++first;
            }
            else{
                ArrayList<Integer> temp = new ArrayList<>();
                for(int i=first;i<second;i++){
                    temp.add(i);
                }
                result.add(temp);
                temp_sum -=first;
                ++first;
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，两个指针移动均单调不减，且最多移动 (sum/2) 次，即方法一提到的枚举的上界，所以时间复杂度为 $O(sum)O(sum)$
• 空间复杂度 :$O(1)O(1)$, 除了答案数组只需要常数的空间存放若干变量