刷题系列博客链接：机试题目
目录
题目及示例
我的题解
滑动窗口结合数学规律
题目及示例
输入一个正整数 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
来源：力扣（LeetCode）
链接：https://leetcode-/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的题解
//这个解法空间复杂度很小，但是时间复杂度稍高，因为没有利用规律，仅是使用滑动窗口class Solution {public int[][] findContinuousSequence(int target) {int start = 1; //开始点，滑动窗口左边界int now = 1; //游标，滑动窗口右边界int sum = 0;List<int[]> list = new ArrayList<>();while(start <= target/2){while(sum < target){sum += now;++now;}if(sum == target){ //找到一组int[] temp = new int[now - start];for (int i = 0; i < temp.length; i++) {temp[i] = start + i;}list.add(temp); //给result赋值 //start到nowstart++; //start = now; //更新开始点now = start; //更新游标sum = 0; //重置和} else if(sum > target){ //开始点不对start++; //start = now; //更新开始点now = start; //更新游标sum = 0; //重置和}}int[][] res = new int[list.size()][];for (int i = 0; i < res.length; i++) {res[i] = list.get(i);}return res;}}
滑动窗口结合数学规律
//若能发现公式xa+x*(x-1)/2=target，x表示每一个一维数组的个数//时空复杂度大大降低class Solution {public int[][] findContinuousSequence(int target) {int[][] array = new int[target/2][];int num = 0;for (int i = 0,x=2; i < target/2; x++) {int ax = target - x*(x-1)/2;if(ax <= 0)break;if(ax%x == 0){num++;int a = ax/x;array[num-1] = new int[x];for (int j = 0; j < x; j++) {array[num-1][j] = a + j;}}i++;}int[][] array1 = new int[num][];for (int i = num-1,j = 0; i >= 0; i--,j++) {array1[j] = array[i];}return array1;}}
