思路及解答暴力枚举

通过双重循环尝试所有可能的序列起点和终点。针对每⼀个索引起点都计算后续的连续⼦数组的和并且将元素存到临时 list 中。如果和不超过 sum ,那么就继续往后⾯遍历如果和等于 sum 则说明该连续⼦数组满⾜条件将临时 list 添加到结果集中如果和⼤于 sum 则说明连续⼦数组已经超过该索引起点的不满⾜条件直接 break 。注意的是起点我们只需要遍历到 sum/2 的位置即可因为⼤于 sum/2 的索引任何两个数的和都⼤于 sum 不符合条件。javaimport java.util.ArrayList; public class Solution { public ArrayListArrayListInteger FindContinuousSequence(int sum) { ArrayListArrayListInteger result new ArrayList(); if (sum 3) return result; // 至少需要两个数最小和为123 // 序列起点最多到sum/2因为至少两个数第二个数肯定比sum/2大 for (int i 1; i sum / 2; i) { int currentSum 0; ArrayListInteger sequence new ArrayList(); // 从i开始累加直到和大于等于sum for (int j i; j sum; j) { currentSum j; sequence.add(j); if (currentSum sum) { result.add(new ArrayList(sequence)); // 找到有效序列 break; } else if (currentSum sum) { break; // 已经超过无需继续 } } } return result; } }时间复杂度O(n²)空间复杂度O(k)k为结果序列数数学计算利用等差数列求和公式进行数学优化减少计算量。思路设序列长度为n起始为x则满足n*(2xn-1)/2 sumjavaimport java.util.ArrayList; public class Solution { public ArrayListArrayListInteger FindContinuousSequence(int sum) { ArrayListArrayListInteger result new ArrayList(); if (sum 3) return result; // 序列长度n从2开始尝试至少两个数 for (int n 2; n * (n 1) / 2 sum; n) { // 根据求和公式推导sum n*(2xn-1)/2 // 解得x (2*sum/n - n 1)/2 int numerator 2 * sum - n * (n - 1); int denominator 2 * n; // x必须是正整数且分子要能整除分母 if (numerator 0 numerator % denominator 0) { int x numerator / denominator; ArrayListInteger sequence new ArrayList(); for (int i 0; i n; i) { sequence.add(x i); } result.add(sequence); } } // 由于我们从长度小的开始需要反转结果保证序列间顺序 result.sort((a, b) - a.get(0) - b.get(0)); return result; } }时间复杂度O(n)空间复杂度O(1)滑动窗口最优使用双指针技术动态调整窗口大小javaimport java.util.ArrayList; public class Solution { public ArrayListArrayListInteger FindContinuousSequence(int sum) { ArrayListArrayListInteger result new ArrayList(); if (sum 3) return result; int left 1; // 窗口左边界 int right 2; // 窗口右边界 int currentSum left right; // 当前窗口和 // 左边界最多到sum/2因为至少需要两个数 while (left sum / 2) { if (currentSum sum) { // 找到有效序列添加到结果 ArrayListInteger sequence new ArrayList(); for (int i left; i right; i) { sequence.add(i); } result.add(sequence); // 左边界右移继续寻找 currentSum - left; left; } else if (currentSum sum) { // 和太小扩大窗口右边界右移 right; currentSum right; } else { // 和太大缩小窗口左边界右移 currentSum - left; left; } } return result; } }