和为

题目

牛客网

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

解题思路

  1. 与上一个题目类似,需要确定的是序列的最大值,不超过 sum
  2. 使用窗口模式,两个指针定义一个窗口,和为 t
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    if (sum == 1) {
        return res;
    }

    int start = 1, end = 2;
    int t = start + end;

    while (start < end) {
        if (t == sum) {
            ArrayList<Integer> ints = new ArrayList<>();
            for (int i = start; i <= end; i++) {
                ints.add(i);
            }
            res.add(ints);
            t -= start;
            start++;
        } else if (t > sum) {
            t -= start;
            start++;
        } else {
            if (end >= sum) break;

            end++;
            t += end;
        }
    }

    return res;
}