41、和为S的两个数

【题目描述】小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

【输出描述】输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。

【解题思路1】暴力解法
//1. 双层循环，找出所有和为S的连续正数序列。

【源码1】

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> arrs = new ArrayList<ArrayList<Integer>>();
        for(int i=1; i<sum; i++){
            int s = 0;
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for(int j=i; j<sum; j++){
                if(s < sum){
                    s += j;
                    arr.add(j);
                    if(s == sum){
                        arrs.add(arr);
                        break;
                    }
                }else{
                    break;
                }
            }
        }
        return arrs;
    }
}

 


【解题思路2】夹逼方案的变体 

//1. 延续题目“和为S的两个数字”的思想。设置一大一小两个指针。 

//2. 初始状态下，small指向1，big指向2。如果从small到big的和大于S，则从序列中去掉较小的值，也就是small向后移动一个位置。若从small到big的序列和小于S，则big向后移动一个位置，以便序列包含更多的数字。 

//3. 因为题目中要求最少是两个数字，所以small最大为（s+1）/2。

【源码2】

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        if(sum<=1){return lists;}
        int small=1;
        int big=2;
        while(small!=(1+sum)/2){          //当small==(1+sum)/2的时候停止
            int curSum=sumOfList(small,big);
            if(curSum==sum){
                ArrayList<Integer> list=new ArrayList<Integer>();
                for(int i=small;i<=big;i++){
                    list.add(i);
                }
                lists.add(list);
                small++;big++;
            }else if(curSum<sum){
                big++;
            }else{
                small++;
            }
        }
        return lists;
    }

    public int sumOfList(int head,int leap){        //计算当前序列的和
        int sum=head;
        for(int i=head+1;i<=leap;i++){
            sum+=i;
        }
        return sum;
    }
}
a. 有个小技巧，每次循环过程中都要求当前连续序列的和，但考虑到每次操作之后的序列和操作之前的序列大部分数字都是一样的，只是增加一位或者减少一位数字，所以我们可以在前一个序列的和基础上求操作之后的序列的和。这样可以减少不必要的运算。


  


【解题思路3】数学公式法 

//1. 从start到end的连续正数序列的和记为sum。 

//2. sum = (start+end)*(end-start+1)/2 

//3. 遍历一次数组，令start为当前遍历值，解上述方程，求出end的值，跟最大值比较，若在给定的数组之内，则为一组解。



链接：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
来源：牛客网

//我竟然解了二元一次方程，我是菜鸟我怕谁。。
//(start+end)*(end-start+1)/2=sum; 
//根据start解出end。。。。。
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
         ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        if(sum<3) return result;
        for(int i=1;i<=sum/2;i++){
            int value=1+4*i*i-4*i+8*sum;
            int valueSqrt=(int)Math.sqrt(value);
            if(value>=25&&valueSqrt*valueSqrt==value){
                ArrayList<Integer> path=new ArrayList<Integer>();
                for(int j=i;j<=(valueSqrt-1)>>1;j++)
                    path.add(j);
                result.add(path);
            }
        }
        return result;
    }