和为S的连续正数序列

我一开始以为自己的解法是暴力解，后来看了答案后才发现自己的想法是符合前缀和解法的思想：

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (sum < 3) 
            return ret;
        int total = (sum + 1) / 2;
        for (int i = 1; i < total; ++i) {
            for (int j = i, s = 0; j <= total; ++j) {
                s += j;
                if (s == sum) {
                    ArrayList<Integer> r = new ArrayList<>();
                    for (int k = i; k <= j; ++k) {
                        r.add(k);
                    }
                    ret.add(r);
                    break;
                } else if (s > sum) {
                    break;
                }
            }
        }
        return ret;
    }
}

后来看了一下题解中的暴力解，用它的思想实现了一遍，与前缀和方法有一定的细微区别：

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (sum < 3) 
            return ret;
        int total = (sum + 1) / 2;
        for (int i = 1; i < total; ++i) {
            for (int j = i + 1; j <= total; ++j) {
                int s = 0;
                for (int k = i; k <=j; ++k) {
                    s += k;
                }
                if (s == sum) {
                    ArrayList<Integer> r = new ArrayList<>();
                    for (int k = i; k <= j; ++k) {
                        r.add(k);
                    }
                    ret.add(r);
                    break;
                } else if (s > sum) {
                    break;
                }
            }
        }
        return ret;
    }
}

最后是滑动窗口解法，这个解法是没有想到的，学习了：

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (sum < 3) 
            return ret;
        int l = 1, r = 1;
        int tmp = 0;
        while (l <= sum / 2) {
            if (tmp < sum) {
                tmp += r;
                ++r;
            } else if (tmp > sum) {
                tmp -= l;
                ++l;
            } else {
                ArrayList<Integer> re = new ArrayList<>();
                for (int k = l; k < r; ++k) {
                    re.add(k);
                }
                ret.add(re);
                tmp -= l;
                ++l;
            }
        }
        return ret;
    }
}