和为s的连续正数序列II
题目
输入一个正整数 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
最简单的想法就是从1遍历到target/2的位置,多次遍历即可.
这里其实可以用到窗口滑动的方法.因为题目要求数字连续,就保证了窗口滑动可以确保所有的结果都适用
在领扣的提交中还有一位大神的解法,我将一位朋友的说明列在下面
一开始的时候，我考虑到了 target%i=0target 的时候，ii 是多少就有多少个元素在这个数组里面，但是我怎么也没想到把他们连在一起，而且我没法按照规律处理两个相邻的数字加在一起的情况。然后我看到了这段代码，豁然开朗，觉得有必要记录下来，感谢这位大哥。
这个题如果用滑动窗口，暴力方法去解决，是完全可以的，但是这道题的数学规律决定了他可以很快。
在这里，我们考虑以 99 为例子，99 可以被拆开成 4+54+5。
为了得到 44 我们需要思考一下。根据规律如果是 [4,5][4,5] 的话，i=2i=2，target % 2 = 0target 其中 [4,5][4,5] 可以改写成 4+(4+1)4+(4+1)。
在考虑三个元素的时候 2+3+42+3+4 我们发现他可以被写成 2+(2+1)+(2+2)2+(2+1)+(2+2) target%3 = 0target。似乎有点规律，我们不妨用 开始元素 xx 元素个数 你会发现如果 targettarget 刚好为这个值的话，也能满足 target%i=0target。
那我们如何让 targettarget 的值等于我们需要的值呢？
根据刚才的变式，我们发现只要让 targettarget 逐次减去 (1,2,3,....)(1,2,3,....) 并且当 target%i = 0target 的时候返回这个 target/itarget/i 就是我们需要的值了。
翻译成 Java，写在了下面：
作者：VaporMax
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/java-shuang-100-by-vapormax/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码
暴力法
//最简单的想法就是从1遍历到target/2的位置,多次遍历即可.
//暴力法
int index = target % 2 == 1?target/2+1:target/2;
int num = 1;
ArrayList<int[]> result = new ArrayList<>();
while(num < index){
int sum = 0;
for(int i = num;i <= index;i++){
sum += i;
if(sum == target){
int[] list = new int[i-num+1];
for(int j = num,int n = 0;j < i+1;j++){
list[n++] = j;
}
result.add(list);
break;
}
if (sum > target){
break;
}
}
num++;
}
return result.toArray(new int[result.size()][]);
窗口滑动的方法
class Solution {
public int[][] findContinuousSequence(int target) {
//可以使用窗口滑动的方法
//窗口的大小就是根据当前窗口的和与目标的对标.大了就缩小窗口,小了就扩大窗口,直到匹配
int leftIndex = 1;
int rightIndex = 1;
int sum = 0;
ArrayList<int[]> result = new ArrayList<>();
while(leftIndex <= target /2){
if(sum < target){
sum += rightIndex;
rightIndex++;
}
if(sum > target){
sum -= leftIndex;
leftIndex++;
}
if (sum == target){
int[] ints = new int[rightIndex-leftIndex];
for(int i = leftIndex;i < rightIndex;i++){
ints[i-leftIndex] = i;
}
result.add(ints);
sum -= leftIndex;
leftIndex++;
}
}
return result.toArray(new int[result.size()][]);
}
}
大神的办法
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> result = new ArrayList<>();
int i = 1;
while(target>0)
{
target -= i++;
if(target>0 && target%i == 0)
{
int[] array = new int[i];
for(int k = target/i, j = 0; k < target/i+i; k++,j++)
{
array[j] = k;
}
result.add(array);
}
}
Collections.reverse(result);
return result.toArray(new int[0][]);
}
}
作者：VaporMax
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/java-shuang-100-by-vapormax/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
网友评论