输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
解题思路:
求一段连续正数序列的和的公式,假设最小数为 $a$,最大数为 $b$,则这段数字的和为:
$$
sum = \frac{(a+b) \times (b - a + 1)}{2}
$$
使用双指针来解题,通过指针 $l$ 和 $r$ ,不断计算 $[l, r]$ 窗口的序列和 $sum$,根据 $sum$ 的大小调整窗口的大小。
- 如果 $sum = target$,说明这段序列和合法,可以记录起来,同时缩小窗口,$l$ 自增;
- 如果 $sum > target$,说明窗口太大,$l$ 自增;
- 如果 $sum < target$,说明窗口太小,$r$ 自增;
代码:
public int[][] findContinuousSequence(int target) {
List<int[]> ans = new ArrayList<>();
for (int l = 1, r = 2; l < r; ) {
int sum = (l + r) * (r - l + 1) / 2;
if (sum == target) {
int[] list = new int[r - l + 1];
for (int i = l; i <= r; i++) {
list[i - l] = i;
}
ans.add(list);
l++;
} else if (sum < target) {
r++;
} else {
l++;
}
}
return ans.toArray(new int[ans.size()][]);
}
复杂度分析:
- 时间复杂度$O(N)$:其中 $N = target$,$l$ 和 $r$ 最终会相遇在 $\frac{N}{2}$ 的位置。
- 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。
评论区