• 和为S的连续正数序列
    • 题目
    • 解题思路

    和为S的连续正数序列

    题目

    牛客网

    输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

    解题思路

    1. 与上一个题目类似,需要确定的是序列的最大值,不超过 sum
    2. 使用窗口模式,两个指针定义一个窗口,和为 t
    1. public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    2. ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    3. if (sum == 1) {
    4. return res;
    5. }
    6. int start = 1, end = 2;
    7. int t = start + end;
    8. while (start < end) {
    9. if (t == sum) {
    10. ArrayList<Integer> ints = new ArrayList<>();
    11. for (int i = start; i <= end; i++) {
    12. ints.add(i);
    13. }
    14. res.add(ints);
    15. t -= start;
    16. start++;
    17. } else if (t > sum) {
    18. t -= start;
    19. start++;
    20. } else {
    21. if (end >= sum) break;
    22. end++;
    23. t += end;
    24. }
    25. }
    26. return res;
    27. }