題⽬描述

⼩明很喜歡數學，有⼀天他在做數學作業時，要求計算出 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<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (sum < 3) return result; // 至少需要兩個數，最小和為1+2=3
        
        // 序列起點最多到sum/2，因為至少兩個數，第二個數肯定比sum/2大
        for (int i = 1; i <= sum / 2; i++) {
            int currentSum = 0;
            ArrayList<Integer> sequence = new ArrayList<>();
            
            // 從i開始累加，直到和大於等於sum
            for (int j = i; j < sum; j++) {
                currentSum += j;
                sequence.add(j);
                
                if (currentSum == sum) {
                    result.add(new ArrayList<>(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<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (sum < 3) return result;
        
        // 序列長度n從2開始嘗試（至少兩個數）
        for (int n = 2; n * (n + 1) / 2 <= sum; n++) {
            // 根據求和公式推導：sum = n*(2x+n-1)/2
            // 解得：x = (2*sum/n - n + 1)/2
            int numerator = 2 * sum - n * (n - 1);
            int denominator = 2 * n;
            
            // x必須是正整數，且分子要能整除分母
            if (numerator > 0 && numerator % denominator == 0) {
                int x = numerator / denominator;
                ArrayList<Integer> sequence = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    sequence.add(x + i);
                }
                result.add(sequence);
            }
        }
        
        // 由於我們從長度小的開始，需要反轉結果保證序列間順序
        result.sort((a, b) -> a.get(0) - b.get(0));
        return result;
    }
}

• 時間複雜度：O(n)
• 空間複雜度：O(1)

滑動窗口（最優）

使用雙指針技術，動態調整窗口大小

import java.util.ArrayList;

public class Solution {

    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (sum < 3) return result;
        
        int left = 1;    // 窗口左邊界
        int right = 2;   // 窗口右邊界
        int currentSum = left + right; // 當前窗口和
        
        // 左邊界最多到sum/2，因為至少需要兩個數
        while (left <= sum / 2) {
            if (currentSum == sum) {
                // 找到有效序列，添加到結果
                ArrayList<Integer> sequence = new ArrayList<>();
                for (int i = left; i <= right; i++) {
                    sequence.add(i);
                }
                result.add(sequence);
                
                // 左邊界右移，繼續尋找
                currentSum -= left;
                left++;
            } else if (currentSum < sum) {
                // 和太小，擴大窗口（右邊界右移）
                right++;
                currentSum += right;
            } else {
                // 和太大，縮小窗口（左邊界右移）
                currentSum -= left;
                left++;
            }
        }
        
        return result;
    }
}

• 時間複雜度：O(n）
• 空間複雜度：O(1)