剑指 Offer 57 - II. 和为s的连续正数序列（简单）

╰+攻爆jí腚メ 2022-09-12 03:53 83阅读 0赞

### 剑指 Offer 57 - II. 和为s的连续正数序列 ###

*   *   *  题目描述
         *  源码
         *   *   *  方法一：数学计算
                 *  方法二：滑动窗口

Leetcode链接：[剑指 Offer 57 - II. 和为s的连续正数序列][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()][]);
        }
    }

[Offer 57 - II. _s]: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/