剑指 Offer.57-II.和为s的连续正数序列
剑指 Offer.57 - II. 和为s的连续正数序列
题目链接
剑指 Offer 57 - II. 和为s的连续正数序列
问题描述
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
个人想法（滑动窗口）
直接想到了滑动窗口，通过双指针能直接实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public int[][] findContinuousSequence(int target) {
int left = 1;
int right = 1;
int windows = 0;
List<int[]> res = new ArrayList<>();
List<Integer> subRes = new ArrayList<>();
while(left <= (target/2)){
if(windows < target){
windows += right;
right++;
}else if(windows > target){
windows -= left;
left++;
}else{
int[] windowsElements = new int[right-left];
for(int i=left;i<right;i++){
windowsElements[i-left] = i;
}
res.add(windowsElements);
windows -= left;
left++;
}
}
return res.toArray(new int[res.size()][]);
}
}
|
在当前窗口达到题目要求时，在将当前解添加进解集后，需要将最左侧的元素删除出窗口，否则会发生死循环
官方解法（求解一元二次方程）
将i,j带入等差数列求和公式后，由于确定target与i，可通过求解公式直接求出解，循环判断，当数字为整数时，将其作为右边界，边界中间的元素即是解。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int[][] findContinuousSequence(int target) {
int i = 1;
double j = 2.0;
List<int[]> res = new ArrayList<>();
while(i < j) {
j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
if(i < j && j == (int)j) {
int[] ans = new int[(int)j - i + 1];
for(int k = i; k <= (int)j; k++)
ans[k - i] = k;
res.add(ans);
}
i++;
}
return res.toArray(new int[0][]);
}
}
作者：jyd
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|