JZ74 和为S的连续正数序列

题目

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

方法1 枚举法

思路

算法实现

从数字1开始枚举连续的数字，将其累加判断其是否等于目标，
如果小于目标数则继续往后累加，
如果大于目标数说明会超过，跳出，
继续枚举下一个数字开始的情况（比如2，比如3），
这样每次都取连续的序列，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序列。

具体做法：
    step 1：从1到目标值一半向下取整作为枚举的左区间，即每次序列开始的位置。
    step 2：从每个区间首部开始，依次往后累加，如果大于目标值说明这一串序列找不到，换下一个起点。
    step 3：如果加到某个数字刚好等于目标值，则记录从区间首到区间尾的数字。

代码

package mid.JZ74和为S的连续正数序列;

import java.util.ArrayList;

public class Solution {
    /**
     * 枚举法
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (sum == 0) return new ArrayList<>();
        //因为序列至少两个数，因此枚举最多到该数字的一半向下取整
        int sum1 = 0;
        int mid = (sum - 1) / 2;
        for (int i = 1; i <= mid; i++) {
            for (int j = i; ; j++) {
                sum1 += j;
                if (sum1 > sum) {
                    sum1 = 0;
                    break;
                } else if (sum1 == sum) {
                    ArrayList<Integer> temp = new ArrayList<>();
                    for (int k = i; k <= j; k++)
                        temp.add(k);
                    res.add(temp);
                    sum1 = 0;
                    break;
                }
            }
        }
        return res;
    }
}

方法2 滑动窗口（推荐使用）

思路

算法实现

从某一个数字开始的连续序列和等于目标数如果有，只能有一个，于是我们可以用这个性质来使区间滑动。

两个指针l、r指向区间首和区间尾，公式(l+r)∗(r−l+1)/2计算区间内部的序列和，
如果这个和刚好等于目标数，说明以该区间首开始的序列找到了，记录下区间内的序列，同时以左边开始的起点就没有序列了，于是左区间收缩；
如果区间和大于目标数，说明该区间过长需要收缩，只能收缩左边；
如果该区间和小于目标数，说明该区间过短需要扩大，只能向右扩大，移动区间尾。

具体做法：
    step 1：从区间[1,2][1,2][1,2]开始找连续子序列。
    step 2：每次用公式计算区间内的和，若是等于目标数，则记录下该区间的所有数字，为一种序列，同时左区间指针向右。
    step 3：若是区间内的序列和小于目标数，只能右区间扩展，若是区间内的序列和大于目标数，只能左区间收缩。

代码

package mid.JZ74和为S的连续正数序列;

import java.util.ArrayList;

public class Solution {
    /**
     * 滑动窗口（推荐使用）
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int l = 1, r = 2; l < r; ) {
            int sum1 = (l + r) * (r - l + 1) / 2;
            if (sum1 == sum) {
                ArrayList<Integer> temp = new ArrayList<>();
                for (int i = l; i <= r; i++) {
                    temp.add(i);
                }
                res.add(temp);
                l++;
            } else if(sum1 < sum) {
                r++;
            } else {
                l++;
            }
        }
        return res;
    }
}