博客

剑指 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 <= 10^5


解题思路

由于序列是严格递增的正整数序列，所以我们可以用

双指针算法

。

1. 设置两个指针
   
i

   和
   
j

   ，分别指向连续正数序列的起始和终止

2. 用
   
sum

   表示当前连续正数序列的和，即
   
sum=i+(i+1)+…+j


3. 以
   
i

   递增的方式遍历整个序列(
   
1到target

   )，代表查找以
   
i

   开头的时候结尾
   
j

   应该是多少，
   
i~j

   的和
   
sum

   才不会小于
   
target

   。所以当
   
sum < target

   时说明
   
j

   应该往后移动，当
   
sum = target

   时，说明满足题意,记录一个结果，当
   
sum > target

   时说明以当前
   
i

   开头的连续正数序列之和不可能等于
   
target

   ，可以去计算下一个以
   
i

   开头的连续正数序列了。

Java代码

class Solution {
    public int[][] findContinuousSequence(int target) {
        //一开始并不知道结果数组中会有多少了结果，即不知道结果数组的长度，因此先用List
        List<int[]> list = new ArrayList<>();

        int sum = 1;//i从1开始，所以sum起始是1
        for(int i = 1,j = 1; i < target;i++){
            while(sum < target) {//j后移到哪个位置时，才能i + (i+1) +... +j >= target
                j++;
                sum += j;
            }
            if(sum == target && j - i > 0){//j - i > 0是题目要求的至少要含两个数
                int[] temp = new int[j - i + 1];
                for(int p = 0,q = i; q <= j; p ++ ,q++){
                    temp[p] = q;
                }
                list.add(temp);
            }
            sum -= i;//当前i移出，计算下一个以i+1开头的正数序列去
        }
		
		//C++中没有不规则数组，故必须指定第二维的大小
		//Java中第二维不写，则说明创建了一个不规则数组（Java核心技术卷I，p89）
        int[][] res = new int[list.size()][];
        for(int i = 0;i < list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
}