原题(来源Leetcode)
输入一个正整数 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
解法
思想
这道题最大的坑就是用二维数组做返回值吧。。确实语法上挺麻烦的,解法就是滑动窗口,一个prev一个next,如果当前区间内的所有值的和小于目标值,next后移一位,如果大于目标值,prev后移一位,如果等于目标值,把当前区间内的所有数放入数组中再放入一个list中。
这样下去直到prev大于目标值的一半,就可以结束循环了,然后将list中所有的数组再搞进一个数组里去。
代码
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> list = new ArrayList<int[]>();
int prev = 1,next = 1;
int sum = 1;
while(next<=(target+1)/2){
if(sum > target){
sum = sum-prev;
prev++;
}else{
if(sum == target){
int[] nums = new int[next-prev+1];
for(int i = 0;i<next-prev+1;i++){
nums[i] = i+prev;
}
list.add(nums);
}
next++;
sum = sum+next;
}
}
int[][] ans = new int[list.size()][];
for(int i = 0;i<list.size();i++){
ans[i] = list.get(i);
}
return ans;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer57-%e5%92%8c%e4%b8%bas%e7%9a%84%e8%bf%9e%e7%bb%ad%e6%ad%a3%e6%95%b0%e5%ba%8f%e5%88%97/