剑指 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
一、枚举+暴力解法
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> vec = new ArrayList<int[]>();
int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
for (int i = 1; i <= limit; ++i) {
for (int j = i;; ++j) {
sum += j;
if (sum > target) {
sum = 0;
break;
} else if (sum == target) {
int[] res = new int[j - i + 1];
for (int k = i; k <= j; ++k) {
res[k - i] = k;
}
vec.add(res);
sum = 0;
break;
}
}
}
return vec.toArray(new int[vec.size()][]);
}
}
二、滑动窗口（双指针）
做题思路：
当s == target时，记录整个连续整数的序列
当s >= target时候，更新元素s,并向右移动左边界i = i + 1
当s < target时候，向右移动右边界j = j + 1并更新元素s
借鉴了K神的思路和图，可通过图片了解程序如何运行的。如下图：
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][]);
}
}