一、题目
输入一个正整数 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，我们来看一下如何进行逻辑操作的，请见下图所示：
image.png
四、代码实现
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][]);
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论