剑指offer 41.和为S的连续正数序列

剑指offer 41.和为S的连续正数序列

题目

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

思路

这一看就是标准的滑动窗口题目，设置左右两个游标，然后计算区间和，若区间和小，那么右侧游标增加，区间和大，左侧游标增加，记得保存符合条件的结果。若左右游标重合，那就可以结束了，因为这个区间至少包括两个数。

代码

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    int l = 1;
    int r = 2;
    while (l < r) {
      int num = (r - l + 1) * (l + r) / 2;
      if (num == sum) {
        ArrayList<Integer> one = new ArrayList<>();
        for (int i = l; i <= r; i++) {
          one.add(i);
        }
        list.add(one);
        r++;
      } else if (sum > num) {
        r++;
      } else {
        l++;
      }
    }
    return list;
  }