图解LeetCode——剑指 Offer 57 - II. 和为s的连续正数序列

一、题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

二、示例

2.1> 示例 1：

【输入】target = 9 【输出】[[2,3,4],[4,5]]

2.2> 示例 2：

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

限制：

• 1 <= target <= 10^5

三、解题思路

根据题目描述，我们可以获得一个非常重要的信息，即：连续正整数序列；那么，我们就可以较为容易的想到采用“滑动窗口”方式进行解题。因为滑动窗口解题的特性就是连续元素并进行统计之类的操作。

既然我们要采用滑动窗口进行解题，我们首先默认创建两个指针，即：指向窗口最前端的head指针，它的默认值为1；以及指向窗口最后端的tail指针，它的默认值为2；

由于我们已经确定了head等于1，tail等于2，那么我们创建sum变量，用于记录滑动窗口中所有元素之和，它的默认值就是head+tail等于3；

随后，我们就可以进行窗口的滑动操作了，具体操作规则如下所示：

【如果sum < target】我们就扩大窗口，执行tail++，并更新sum值（sum加上tail值）； 【如果sum > target】我们就缩小窗口，更新sum值（sum减去head值），执行head++； 【如果sum == target】表示我们到了符合条件的数字集合。然后，执行head++；

当head等于tail的时候，就可以终止窗口滑动操作了。为什么是这样呢？我们假设窗口里只有4和5，target等于9，那么满足条件后，我们需要将数字4踢出窗口，并增加数字6，那么此时我们发现，窗口里存在5和6了，大于target，并且后续无论怎么滑动，窗口内的元素之和都是大于9的（题目要求窗口内至少含有两个数）。

解题思路就是这些了，为了便于理解，我们还是举一个例子，例如：target=9，我们来看一下如何进行逻辑操作的，请见下图所示：

四、代码实现

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> result = new ArrayList();
        int head = 1, tail = head + 1, sum = head + tail;
        while(head != tail) {
            if (sum < target) sum += ++tail; // 滑动窗口外扩
            else if (sum > target) sum -= head++; // 滑动窗口内收
            else {
                int[] res = new int[tail - head + 1];
                for (int i = head, index = 0; i <= tail; i++) res[index++] = i;
                result.add(res);
                sum -= head++; // 滑动窗口内收
            }     
        }
        return result.toArray(new int[0][]);
    }
}