劍指 Offer 57 - II. 和為s的連續正數序列（簡單）

劍指 Offer 57 - II. 和為s的連續正數序列

• • • 題目描述
    • 源碼
    • • • 方法一：數學計算
        • 方法二：滑動視窗

Leetcode連結：劍指 Offer 57 - II. 和為s的連續正數序列

題目描述

輸入一個正整數

target

，輸出所有和為 target 的連續正整數序列（至少含有兩個數）。

序列内的數字由小到大排列，不同序列按照首個數字從小到大排列。

示例 1：

輸入：target = 9

輸出：[[2,3,4],[4,5]]

示例 2：

輸入：target = 15

輸出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 105

源碼

方法一：數學計算

class Solution {
    //1. 求和公式 Sn = n(a1 + an)/2
    public int[][] findContinuousSequence(int target) {
        ArrayList<int[]> res = new ArrayList<>();
        int i = 1;
        int j = 2;
        while(j < target){
        	//求和
            double sum = (j - i + 1) * (j + i) * 0.5;
            if((int)sum == target){
                int[] item = new int[j - i + 1];
                for(int k = i; k <= j; k ++){
                    item[k - i] = k;
                }
                res.add(item);
                i++;
                j = i + 1;
            }else if(sum < target){
                j ++;
            }else if(sum > target){
                i ++;
                j = i + 1;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
           

方法二：滑動視窗

class Solution {
    //2. 滑動視窗
    public int[][] findContinuousSequence(int target) {
        int i = 1;
        int j = 2;
        int sum = 3;
        ArrayList<int[]> res = new ArrayList<>();
        
        while(i < j){
            if(sum == target){
                int[] item = new int[j - i + 1];
                for(int k = i; k <= j; k ++){
                    item[k - i] = k;
                }
                res.add(item);
            }
            if(sum >= target){
                sum -= i;
                i ++;
            }else if(sum < target){
                j ++;
                sum += j;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}