每日算法之和为S的连续正数序列

JZ74 和为S的连续正数序列

题目

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

复制代码

方法1 枚举法

思路

算法实现

1. 从数字1开始枚举连续的数字，将其累加判断其是否等于目标，
2. 如果小于目标数则继续往后累加，
3. 如果大于目标数说明会超过，跳出，
4. 继续枚举下一个数字开始的情况（比如2，比如3），
5. 这样每次都取连续的序列，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序列。
7. 具体做法：
8.     step 1：从1到目标值一半向下取整作为枚举的左区间，即每次序列开始的位置。
9.     step 2：从每个区间首部开始，依次往后累加，如果大于目标值说明这一串序列找不到，换下一个起点。
10.     step 3：如果加到某个数字刚好等于目标值，则记录从区间首到区间尾的数字。

复制代码

代码

[code]package mid.JZ74和为S的连续正数序列;import java.util.ArrayList;public class Solution {    /**     * 枚举法     * @param sum     * @return     */    public ArrayList FindContinuousSequence(int sum) {        ArrayList res = new ArrayList();        if (sum == 0) return new ArrayList();        //因为序列至少两个数，因此枚举最多到该数字的一半向下取整        int sum1 = 0;        int mid = (sum - 1) / 2;        for (int i = 1; i  sum) {                    sum1 = 0;                    break;                } else if (sum1 == sum) {                    ArrayList temp = new ArrayList();                    for (int k = i; k