窮舉- 和為S的連續正數序列-JZ41

描述

小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正确答案是100。但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)。沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22。現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? Good Luck!

傳回值描述：

輸出所有和為S的連續正數序列。序列内按照從小至大的順序，序列間按照開始數字從小到大的順序

示例1

輸入： 9

傳回值： [[2,3,4],[4,5]]

思路：

利用滑動視窗的思想，記錄連續序列的左右邊界以及臨時序列和temp

分為三種情況

• temp > s 左邊界增大
• temp < s 右邊界增大
• temp == s 記錄此序列并增大右邊界

注意：序列至少包括兩個數，是以左邊界最大不超過(s+1)/2

看代碼有循環嵌套，但是其實第二個for循環很少會執行，是以

時間複雜度：O(n)

空間複雜度：O(1)

代碼：

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (sum < 3) {
        	//和最小為3 否則不滿足序列至少包括兩個數的要求
            return result;
        }
        int left = 1; //連續序列最小值
        int right = 2;//連續序列最大值
        int temp = 3; //臨時序列和
        //至少包括兩個數 是以連續序列最小值必須小于(sum+1)/2
        while (left < (sum+1)/2) {
            if (temp > sum) {
                temp -= left;
                left++;
                continue;
            }
            if (temp < sum) {
                right++;
                temp += right;
                continue;
            }
            //符合題目要求 temp == sum
            ArrayList<Integer> newArr =  new ArrayList<>();
            for (int k = left; k <= right; k++) {
                newArr.add(k);
            }
            result.add(newArr);
            
            right++;
            temp += right;
        }
        return result;
    }
}
           

增加擴充思路

參考代碼

function FindContinuousSequence(sum)
{
    const res = [];
    if(sum <= 0) return res;
    let n=2, x0, each;
    while(n**2 + n <= 2*sum){
        x0 = (2*sum + n -  n**2) / (2*n);
        if(Math.floor(x0) === x0){
            each = [];
            for(let i=0; i<n; ++i) each.push(x0+i);
            res.push(each);
        }
        ++n;
    }
    return res.sort((a, b) => a[0]-b[0]);
}