题目描述
输入一个正整数 target
,输出所有和为 target
的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
示例 1:
1 2
| 输入:target = 9 输出:[[2,3,4],[4,5]]
|
示例 2:
1 2
| 输入:target = 15 输出:[[1,2,3,4,5],[4,5,6],[7,8]]
|
限制:
解法
- 滑动窗口
- 套滑动窗口模板,l是窗口左边界,r是窗口右边界,窗口中的值一定是连续值。
- 当窗口中数字和小于target时,r右移; 大于target时,l右移; 等于target时就获得了一个解
- 答案中会出现的最大数字
(target+1)/2
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 33 34 35 36 37 38 39 40
| class Solution { public int[][] findContinuousSequence(int target) { List<int[]> res=new ArrayList<>(); int left=1; int right=2; int maxNum=(target+1)/2; int tmpSum=left+right; while (right<=maxNum){ if (tmpSum<target){ right++; tmpSum+=right; } else if (tmpSum>target){ tmpSum-=left; left++; } else{ int innerLen=right-left+1; int []temRes=new int[innerLen]; for (int i = 0; i < innerLen; i++) { temRes[i]=left+i; } res.add(temRes); left++; right++; tmpSum+=innerLen; } } int[][] realRes=new int[res.size()][]; return res.toArray(realRes); } }
|
来源:力扣(LeetCode)
链接:剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣(LeetCode)