NowCoder

题目描述

输出所有和为 S 的连续正数序列。

例如和为 100 的连续序列有：

[9, 10, 11, 12, 13, 14, 15, 16]
[18, 19, 20, 21, 22]。

解题思路

双指针

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int tar) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for(int i = 1, j = 1, sum = 1; i < tar; i++) {
        	// 连续的一段
            while(sum < tar) {
                j++;
                sum += j;
            }
            if(sum == tar && j - i >= 1) {
                ArrayList<Integer> arr = new ArrayList<>();
                for(int k = i; k <= j; k++) 
                    arr.add(k);
                res.add(arr);
            }
            sum -= i;
            // i变大同时j变大
        }
        return res;
    }
}

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    int start = 1, end = 2;
    int curSum = 3;
    while (end < sum) {
        if (curSum > sum) {
            curSum -= start;
            start++;
        } else if (curSum < sum) {
            end++;
            curSum += end;
        } else {
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = start; i <= end; i++)
                list.add(i);
            ret.add(list);
            curSum -= start;
            start++;
            end++;
            curSum += end;
        }
    }
    return ret;
}