题目:小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
思路:有两个指针,一个指向开始,一个指向末尾,求和用等差数列的公式;在和等于指定的数时,放到一维数组中,尾指针加1;在和小于指定数时,尾指针加1;大于时,手指针加1。
代码:
public ArrayList<ArrayList<integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<integer>> p=new ArrayList<ArrayList<integer>>();
//有两个指针,一个指向头,一个指向尾
//因为是连续的,构成等差数列,用等差数列的求和公式
int low=1,hight=2;
while(low<hight) {
int temp=(low+hight)*(hight-low+1)/2;
//如果相等,说明这个连续的数列可以构成和为sum
if(temp==sum) {
ArrayList<integer> a=new ArrayList<integer>();
for(int i=low;i<=hight;i++) {
a.add(i);
}
p.add(a);
//继续找下一组
low++;
}else if (temp<sum) {
hight++;
}else {
low++;
}
}
return p;
}</integer></integer></integer></integer></integer>