该题目有几个点需要注意一下:
1 . 这个链表是连续的正数序列,且最少为两个数。
2 . 由于1中的特性,所以数组的和可以用公式计算。(1加到100的那种方法求和,即为:(1+100)*100 / 2)。
貌似题目也只有这两个点需要注意,接下来就是核心算法了,三个概念:1.数组内的数。2.数组实际和。3. 数组目标和。
当数组实际和=目标和时,为了继续寻找可以实现目标和的数组,需要把小数和大数都前移1位;
当数组实际和>目标和时,把小数往前移一位,这样数组内的数就少了最小的一个数,在做比较。
当数组实际和<目标和时,把大数往前移一位,这样数组内的数就增加了一个大数,再比比啊。
using System.Collections.Generic;
class Solution
{
public List<List<int>> FindContinuousSequence(int sum)
{
// write code here
// 定义最终输出数组
List<List<int>> ret = new List<List<int>>();
// 定义i=1,j=2,原因:
int i = 1, j = 2;
// 方法停止条件:1.因为最终输出数组最少为2个数,所以小的那个数不能超过sum的一半,超过了相加就大于sum了,而且小数必须小于大数
while(i < (sum + 1) / 2 && i < j)
{
// 因为是连续的数,所以求和公式可以为(小数+大数)*长度/2;(举例:1加到100怎么算)
int tmpSum = (i + j) * (j - i + 1) / 2;
// 要是数组和小于目标数,需要让大数增加以下
if(tmpSum < sum)
{
j++;
}
// 相等就输出咯
else if(tmpSum == sum)
{
// 定义一个数组,数组长度就是i-j之间的长度
int[] ary = new int[j - i + 1];
// 执行循环,得出数组从i-j
for(int k = i, l = 0; k <= j; k++, l++)
{
ary[l] = k;
}
// 这个数组添加到定义的那个链表
ret.Add(new List<int>(ary));
// 如果还存在其他的怎么办呢,所以要执行i++h和j++
i++;
j++;
}
// 要是数组和大于目标数,把小数加1,这样数组里的数就变少了对吧
else
{
i++;
}
}
// 返回那个链表
return ret;
}
}