一、题目描述

输入一个正整数 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

二、思路讲解

很容易想到双指针滑动窗口。i，j两个指针构成窗口，i在前j在后，从1开始向后滑动，1 2 3 4……。若窗口内数字的和小于target，j后移，扩大窗口；若大于target，i后移，缩小窗口。

三、Java代码实现

class Solution {

    public int[][] findContinuousSequence(int target) {

        int i=1, j=1;
        int sum = 1;
        List<int []> list = new ArrayList<>();
        while(i<=(target/2+1)) {
            while(sum<=target) {
                j++;
                sum = sum + j;
                if(sum==target) {
                    int []temp = new int[j-i+1];
                    for (int k=0; k<temp.length; k++) {
                        temp[k] = i+k;
                    }
                    list.add(temp);
                    break;
                }
            }
            while(i<=(target/2+1) && sum>=target) {
                sum = sum - i;
                i++;
                if(sum==target) {
                    int []temp = new int[j-i+1];
                    for (int k=0; k<temp.length; k++) {
                        temp[k] = i+k;
                    }
                    list.add(temp);
                    break;
                }
            }
        }
        return list.toArray(new int[0][]);
    }
}

贴一个力扣上的更简洁的代码，核心思想是一样的，复杂度也相同：

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i < j) {
            if(s == target) {
                int[] ans = new int[j - i + 1];
                for(int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if(s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

作者：jyd
链接：https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/jian-zhi-offer-57-ii-he-wei-s-de-lian-xu-t85z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124980.html