题目示例输入一个正整数 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
题目要求连续两个以上的正整数之后等于给定的值，这题有两种解法，一种是枚举，一种是利用等差数列求和的方法来解决这个问题。
解法一：枚举枚举方法就是利用双层遍历，第一层遍历的终止条件为给定值的一半，例如给定target=15，那么第一层的终止条件为7.5，第二层的终止条件为连续数之和大于target。
1、解题代码：
class Solution {
public int[][] findContinuousSequence(int target) {
// 存放最终的结果集
List result = new ArrayList<>();
// 遍历总和
int sum = 0;
// 枚举
for (int i = 1; i <= target / 2; i++) {
for (int j = i; ; j++) {
sum += j;
// 如果sum 大于 target 直接返回
if(sum > target) {
sum = 0;
break;
}
if (sum == target){
// 枚举 n 到 m 之间的元素
int[] temp = new int[j - i + 1];
int n = i;
for (int x = 0; x < temp.length; x++) {
// 题目有要求 按照从小到大的顺序排列
temp[x] = n;
n++;
}
result.add(temp);
break;
}
}
}
return result.toArray(new int[0][]);
}
}
复杂度分析
时间复杂度：需要遍历一次数组，所以时间复杂度是O(N^2)
空间复杂度：在这个过程中使用到临时数组，理论上这个临时数组无限的啊，所以空间复杂度为O(N)
解法二：等差数列求和法连续正整数之和，可以利用等差数列求和来解决，等差数列求和公式为：sum=((n+m)*(m-n+1))/2。等差数列求和可以减少遍历项，从而提高效率。
求和方法会出现三种情况：
- sum = target，说明区间[n,m]是一个解
- sum > target，说明区间[n,m]不是一个解，这是需要将首项n 往后移动一位来减少区间的项数，从而减少 sum 的值。
- sum < target，说明区间[n,m]不是一个解，这种情况下需要将尾项 m 向后移动一位，来扩大区间的项数，增大sum 的值。
1、解题代码
class Solution {
public int[][] findContinuousSequence(int target) {
// 存放最终的结果集
List result = new ArrayList<>();
// n：低位数字 m：高位数字
int n = 1, m = 2;
while (n < m) {
// 等差数列求和
int sum = ((n + m) * (m - n + 1)) / 2;
if (sum == target) {
// 枚举 n 到 m 之间的元素
int[] temp = new int[m - n + 1];
int j = n;
for (int i = 0; i < temp.length; i++) {
temp[i] = j;
j++;
}
result.add(temp);
// 前指针向前移动
n++;
} else if (sum < target) {
m++;
} else {
n++;
}
}
return result.toArray(new int[0][0]);
}
}
复杂度分析
时间复杂度：需要遍历一次数组，所以时间复杂度是O(N)
空间复杂度：在这个过程中使用到临时数组，理论上这个临时数组无限的啊，所以空间复杂度为O(N)
这两种解法根据 leetcode 上的提交结果来看，性能和效率上相差不大，但是求和法相对稳定。
以上就是我的两种解法，不知道小伙伴们是如何解这题的，欢迎在留言区亮出你的解法。
互联网平头哥（id：pingtouge_java）
作者：平头哥，学会伺机而动，实现弯道超车
