题解 |#合为s的连续正数序列#

1.构造前缀合数组

2.遍历数组，找到sum-arr[i]是否存在，存在就是一组答案（问题等价数组中找两个合为sum的值）

3.构造答案

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
       int i,j;
       int n = sum/2+1;
       int[] arr = new int[n+1];
       Map<Integer,Integer> map = new HashMap<>();
       ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        
       for(i=1;i<=n;i++)arr[i] = i+arr[i-1];//前缀和数组
       for(i=0;i<=n;i++){
           if(map.containsKey(arr[i]-sum)){
               ArrayList<Integer> list = new ArrayList<>();
               for(j = map.get(arr[i]-sum)+1; j<=i;j++)list.add(j);
               if(list.size()>1)ans.add(list);//至少含两数
           }
           map.put(arr[i],i);
       }
       return ans;
    }
}