剑指 Offer 57 - II 和为s的连续正数序列
2022-01-15 本文已影响0人
itbird01
题目.png
题意:输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
解题思路
解法1:
1.和为target,所以值最大不会超过target / 2 + 1
2.输出结果需要二维数组,但是由给出的例子分析,每个结果数组可能长度不唯一,所以暂时先以list存储结果数据
3.从1开始遍历,到target / 2 + 1,如果遇到sum==target
,则将结果保存,保存之后,回退遍历指针为上一次+1
解题遇到的问题
无
后续需要总结学习的知识点
无
##解法1
import java.util.ArrayList;
import java.util.List;
class Solution {
public int[][] findContinuousSequence(int target) {
int k = target / 2 + 1;
int sum = 0;
List<List<Integer>> list = new ArrayList<List<Integer>>();
for (int i = 1; i <= k; i++) {
sum = 0;
for (int l = i; sum <= target; l++) {
sum += l;
if (sum == target) {
List<Integer> temp = new ArrayList<Integer>();
for (int l2 = i; l2 <= l; l2++) {
temp.add(l2);
}
list.add(temp);
break;
}
}
}
int[][] ans = new int[list.size()][];
for (int i = 0; i < ans.length; i++) {
int[] m = new int[list.get(i).size()];
for (int l = 0; l < list.get(i).size(); l++) {
m[l] = list.get(i).get(l);
}
ans[i] = m;
}
return ans;
}
}