“对于程序员而言，刷了Leetcode不一定能拿offer，但是不刷肯定拿不到offer。”
剑指 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
Solution
滑动窗口（双指针）
通过双指针，不断向右滑动：
$$
T(n) = O(n)
$$
$$
V(n) = O(1)
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[][] findContinuousSequence(int target) {
if (target < 2) return new int[0][0];
List<int[]> res = new ArrayList<>();
int start = 1;
int end = 2;
while (start < end) {
int sum = (start + end)*(end - start + 1)/2;
if (sum < target) end++;
else if (sum > target) start++;
else {
int[] x = new int[end - start + 1];
for (int i = 0; i < x.length; i++) x[i] = start + i;
res.add(x);
start++;
end++;
}
}
return res.toArray(new int[res.size()][]);
}
}
|
数学法
设子序列起始为a，长度为n，利用等差数列求和性质： target = (a + (a + n-1))*n/2; ，求得a与n的关系式，并通过遍历n，确定a的值。
- 1<= a <= target/2
- 2<= n < target
$$
T(n) = O(\sqrt n)
$$
$$
V(n) = O(1)
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[][] findContinuousSequence(int target) {
if (target < 2) return new int[0][0];
List<int[]> res = new ArrayList<>();
for(int n=2; n<target; n++) {
int temp = target - (n-1)*n/2;
if (temp < n) break;
else if (temp % n == 0) {
int a = temp / n;
int[] x = new int[n];
for (int i=0; i<n; i++) x[i] = i+a;
res.add(x);
}
}
Collections.reverse(res);
return res.toArray(new int[res.size()][]);
}
}
|
