题解 | #和为S的连续正数序列#

受到题解的启发，用前缀和先预处理一下，然后再结合前面写过的一个题：求和为目标值的两数下标 的思路，将sum+前缀和处理结果q[i]的值存入map，当下一个q[i]值在map内(记后一个i为j)，就说明：q[j] = sum + q[i] -> q[j]-q[i] =sum 所以答案之一就是 j+1到i的区间之和。
有一个坑就是map要初始化一个(sum,0)的值，不然从1开始加的那个序列会被丢掉~

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > ans = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        int[] q = new int[sum];
        //存入0的初始值
        q[0] = 0;
        map.put(sum,0);
        //计算前缀和,对比q[i]是否存在，并同时把sum+前缀和的结果写进map
        for(int i=1;i<sum;i++){
            q[i] = q[i-1]+i;
            //存在对应值，即取之前的那个存在map的i值+1和目前的i值区间求和，就是答案之一
            if(map.containsKey(q[i])){
                int f = map.get(q[i]);
                ArrayList<Integer> ans1 = new ArrayList<>();
                for(int j = f+1;j<=i;j++){
                    ans1.add(j);
                }
                ans.add(ans1);
                map.put(sum+q[i],i);
                //不可能出现同一个数结尾的情况，所以可以把q[i]删了
                map.remove(q[i]);
            }else{
                map.put(sum+q[i],i);
            }
        }
        return ans;
    }
}