题⽬描述

⼩明很喜欢数学，有⼀天他在做数学作业时，要求计算出 9~16 的和，他⻢上就写出了正确答案是 100 。但是他并不满⾜于此，他在想究竟有多少种连续的正数序列的和为 100 (⾄少包括两个数)。没多久，他就得到另⼀组连续正数和为 100 的序列: 18,19,20,21,22 。现在把问题交给你，你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

返回值描述：输出所有和为 S 的连续正数序列。序列内按照从⼩⾄⼤的顺序，序列间按照开始数字从⼩到⼤的顺序

示例1：

输⼊：9
返回值：[[2,3,4],[4,5]]

思路及解答

暴力枚举

通过双重循环尝试所有可能的序列起点和终点。

针对每⼀个索引起点，都计算后续的连续⼦数组的和，并且将元素存到临时 list 中。

如果和不超过 sum ,那么就继续往后⾯遍历；

如果和等于 sum ，则说明该连续⼦数组满⾜条件，将临时 list 添加到结果集中

如果和⼤于 sum ，则说明连续⼦数组已经超过，该索引起点的不满⾜条件，直接 break 。

注意的是，起点我们只需要遍历到 sum/2 的位置即可，因为⼤于 sum/2 的索引，任何两个数的和都⼤于 sum ，不符合条件。

import java.util.ArrayList;

public class Solution {

    public ArrayList> FindContinuousSequence(int sum) {
        ArrayList> result = new ArrayList();
        if (sum  sequence = new ArrayList();
            
            // 从i开始累加，直到和大于等于sum
            for (int j = i; j (sequence)); // 找到有效序列
                    break;
                } else if (currentSum > sum) {
                    break; // 已经超过，无需继续
                }
            }
        }
        return result;
    }
}

• 时间复杂度：O(n²)
• 空间复杂度：O(k)，k为结果序列数

数学计算

利用等差数列求和公式进行数学优化，减少计算量。

思路：设序列长度为n，起始为x，则满足：n*(2x+n-1)/2 = sum

import java.util.ArrayList;

public class Solution {

    public ArrayList> FindContinuousSequence(int sum) {
        ArrayList> result = new ArrayList();
        if (sum  0 && numerator % denominator == 0) {
                int x = numerator / denominator;
                ArrayList sequence = new ArrayList();
                for (int i = 0; i  a.get(0) - b.get(0));
        return result;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

滑动窗口（最优）

使用双指针技术，动态调整窗口大小

import java.util.ArrayList;

public class Solution {

    public ArrayList> FindContinuousSequence(int sum) {
        ArrayList> result = new ArrayList();
        if (sum  sequence = new ArrayList();
                for (int i = left; i 

• 时间复杂度：O(n）
• 空间复杂度：O(1)

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top