剑指offer - 和为S的连续正数序列(Java实现)

题目链接：https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&&tqId=11194&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：直接遍历左边界和右边界，使用数学的方法来计算这一段连续序列的和，如果和为给定值则保存下来，并且放入答案中。

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       ArrayList<ArrayList<Integer>> list = new ArrayList<>();
       for(int l = 1; l <= (sum + 1) / 2; ++ l) { //左边界
           for(int r = l + 1; r <= (sum + 1) / 2; ++ r) {//右边界
               int _sum = (r - l + 1) * (l + r) / 2;
               if(_sum == sum) {
                   ArrayList<Integer> temp = new ArrayList<>();
                   for(int i = l; i <= r; ++ i) {
                       temp.add(i);
                   }
                   list.add(temp);
               }
           }
       }
       return list;
    }
}

  思路二：双指针，类似于滑动窗口，首先一开始我们先固定一个长度为 2 的一个区间，如果这个区间和小于给定值我们就可以让右指针后移一位，重复这种操作直到区间和不小于给定值，接着如果区间和小于给定值，那么我们就让左指针后移一位，直到区间和不大于给定值，此时的区间和有可能等于给定值，那么我们判断，如果等于给定值则保存答案，此时将左指针后移一位以便于统计后面符合条件的区间。

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       ArrayList<ArrayList<Integer>> list = new ArrayList<>();
       int l = 1, r = 2, _sum = 3;
       while(r <= (sum + 1) / 2) { //右指针不越界
           while(r <= (sum + 1) / 2 && _sum < sum) {//不断的添加数字
               ++ r;
               _sum += r;
           }
           while(l <= r && _sum > sum) {//如果和比较大则不断的删除数字
               _sum -= l;
               ++ l;
           }
           if(r >= l + 1 && _sum == sum) {//找到答案,并且保证区间最小为二
               ArrayList<Integer> temp = new ArrayList<>();
               for(int i = l; i <= r; ++ i) {
                   temp.add(i);
               }
               list.add(temp);
               _sum -= l; ++ l;//可能不止一个答案，删除小的数字继续找一个合适的区间
           }
       }
        return list;
    }
}