和为S的连续正数序列

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

示例：

输入：target = 9
输出：[[2,3,4],[4,5]]

思路

1.这道题可以使用“滑动窗口”+“双指针”的思想解决。
2.设置两个指针，这两个指针用于标识目前所属的范围。

• 当前范围内的和，可以通过等差数列的求和公式 sum=(low+high)*(high-low+1)/2 求出
• 当sum>target时，low指针右移
• 当sum<target时，high指针右移
• 当sum == target时，存下当前范围内的数字
• 当low >= high时，终止操作

Java代码实现

public class Solution {
    public int[][] findContinuousSequence(int sum) {
        ArrayList<int[]> res = new ArrayList<>();
        int low = 1;
        int high = 2;
        while(low < high){
            int cur = (low+high)*(high-low+1)/2;
            if(cur == sum){
                int[] array = new int[high-low+1];
                for (int i = low; i <= high; i++) {
                    array[i-low] = i;
                }
                res.add(array);
                low++;
                high++;
            }else if(cur > sum){
                low++;
            }else{
                high++;
            }
        }
        int[][] resArray = new int[res.size()][];
        return res.toArray(resArray);
    }
}

Golang代码实现

func findContinuousSequence(target int) [][]int {
    res := make([][]int,0)

    low,high := 1,2

    for low < high{
        cur := (low+high) * (high-low+1) / 2
        if cur == target{
            curSlice := make([]int,high-low+1)
            for i:=low;i<=high;i++{
                curSlice[i-low] = i
            }
            res = append(res, curSlice)
            low++
            high++
        }else if cur < target{
            high++
        }else{
            low++
        }
    }
    return res
}