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

太过爱你忘了你带给我的痛 2023-09-27 12:21 62阅读 0赞

> **难度等级：简单**

> **上一篇算法：**
> 
> [剑指 Offer 57. 和为s的两个数字【查找排序】][Offer 57. _s]

> **力扣此题地址：**
> 
> [剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode）][Offer 57 - II. _s_ - _LeetCode]

### 1.题目：和为s的连续正数序列 ###

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

**示例 ：**

>     输入：target = 15
>     输出：[[1,2,3,4,5],[4,5,6],[7,8]]

### 2.解题思路： ###

> **思路，双指针(left左指针 right右指针)**  
> 刚开始 left 在位置 1， right 在位置 2， 定义左右指针之间的数字和为：
> 
> sum = n\*(a1+an)/2 递增数列的求和公式
> 
> 1.类似二分查找的逻辑，当 sum 等于 target 时，将左右指针之间的这种数组加入结果，然后左指针右移  
> 2.当 sum 小于 target 时，右指针右移增大 sum  
> 3.当 sum 大于 target 时，说明以 left 为起点组成的数组不符要求，左指针右移

![a5b385e774ed2e697c8b28cf767c7966.png][]

### 3.代码实现： ###

class Solution {
        public int[][] findContinuousSequence(int target) {
    
            //创建结果数组
            List<int[]> list = new ArrayList<>();
    
            int left = 1;
            int right = 2;
    
            //终止条件是左指针移动到右指针位置，说明此时已经不存在两个数之和能小于 target 了
            while (left < right) {
    
                int sum = (right - left + 1) * (left + right) / 2;
    
                if (sum == target) {
                    //创建数组存储左右指针之间的数组组合
                    int[] tmp = new int[right - left + 1];
    
                    for (int i = 0; i < right - left + 1; i++) {
                        tmp[i] = left + i;
                    }
    
                    //将临时数组结果存储入List
                    list.add(tmp);
    
                    //继续探索下一种方案
                    ++left;
                }else if (sum<target){
                    ++right;
                }else {
                    ++left;
                }
    
            }
            
            //掌握此种二维list转数组方法
            return list.toArray(new int[list.size()][]);
        }
    }

[Offer 57. _s]: https://blog.csdn.net/m0_51697147/article/details/127548521
[Offer 57 - II. _s_ - _LeetCode]: https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/comments/
[a5b385e774ed2e697c8b28cf767c7966.png]: https://img-blog.csdnimg.cn/img_convert/a5b385e774ed2e697c8b28cf767c7966.png