538，剑指 Offer-和为s的连续正数序列

Original 博哥数据结构和算法 2022-05-01

收录于合集 #剑指offer 34个

You can know everything in the world, but the only way you're findin' out that one is by givin' it a shot.

你可以了解世间万物，但追根溯源的唯一途径便是亲身尝试。

问题描述

输入一个正整数target，输出所有和为target的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

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

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5

滑动窗口解决

滑动窗口，这里也叫双指针，因为题中要求的是正整数，连续的，并且至少含有两个数。所以我们使用两个指针，一个left指向1，一个right指向2，他们分别表示窗口的左边界和右边界。然后计算窗口内元素的和。

如果窗口内的值大于target，说明窗口大了，left往右移一步。
如果窗口内的值小于target，说明窗口小了，right往右移一步。
如果窗口内的值等于target，说明找到了一组满足条件的序列，把它加入到列表中

我们以示例1为例来看下视频演示

因为至少有两个数，所以窗口的左边界left <= target / 2，题中是把找到的序列添加到列表list中，最后在转化为二维数组，来看下代码

 1public int[][] findContinuousSequence(int target) {
 2    int left = 1; // 滑动窗口的左边界
 3    int right = 2; // 滑动窗口的右边界
 4    int sum = left + right; // 滑动窗口中数字的和
 5    List<int[]> res = new ArrayList<>();
 6    //窗口的左边是窗口内的最小数字，只能小于等于target / 2,
 7    //因为题中要求的是至少含有两个数
 8    while (left <= target / 2) {
 9        if (sum < target) {
10            //如果窗口内的值比较小，右边界继续向右移动，
11            //来扩大窗口
12            sum += ++right;
13        } else if (sum > target) {
14            //如果窗口内的值比较大，左边边界往右移动，
15            //缩小窗口
16            sum -= left++;
17        } else {
18            //如果窗口内的值正好等于target，就把窗口内的值记录
19            //下来，然后窗口的左边和右边同时往右移一步
20            int[] arr = new int[right - left + 1];
21            for (int k = left; k <= right; k++) {
22                arr[k - left] = k;
23            }
24            res.add(arr);
25            //左边和右边同时往右移一位
26            sum -= left++;
27            sum += ++right;
28        }
29    }
30    //把结果转化为数组
31    return res.toArray(new int[res.size()][]);
32}

数学公式解决

我们假设有一组序列满足条件，其中序列的第一个数是a，他们分别是a，a+1，a+2，……，a+(n-1)，总共有n项，根据求和公式我们可以得出S=n*a+n*(n-1)/2，而S其实就是target，我们简写成t，来研究一下这个公式

要想求a，我们可以通过循环枚举n的值，只有a是正整数的时候才满足条件，那么这个循环什么时候终止呢，其实很简单，当分子t-n*(n-1)/2小于等于0的时候就可以终止了。

因为题中说了最少要有2个数，所以n从2开始，来看下代码

 1public int[][] findContinuousSequence(int target) {
 2    List<int[]> res = new ArrayList<>();
 3    int n = 2;
 4    //死循环
 5    while (true) {
 6        int total = target - n * (n - 1) / 2;
 7        //当分子小于等于0的时候，退出循环
 8        if (total <= 0)
 9            break;
10        //如果首项是正整数，满足条件
11        if (total % n == 0) {
12            int[] arr = new int[n];
13            //找出首项的值
14            int startValue = total / n;
15            for (int k = 0; k < n; k++) {
16                arr[k] = startValue + k;
17            }
18            res.add(arr);
19        }
20        //继续找
21        n++;
22    }
23    //反转，比如当target等于9的时候，结果是
24    //[[4,5],[2,3,4]]，但题中要求的是不同
25    // 序列按照首个数字从小到大排列，所以这里反转一下
26    Collections.reverse(res);
27    //把list转化为数组
28    return res.toArray(new int[res.size()][]);
29}

数学的另一种解决方式

我们来思考这样一个问题

假如target是两个连续数字的和，那么这个序列的首项就是(target-1)/2。
假如target是三个连续数字的和，那么这个序列的首项就是(target-1-2)/3。
假如target是四个连续数字的和，那么这个序列的首项就是(target-1-2-3)/4。
……

证明也很好证，我们随便找一个，假如target是四个连续的序列和，那么这四个数字就是

a，a+1,a+2,a+3

也就是

4*a+1+2+3=target

所以他们的首项

a=(target-1-2-3)/4。

搞懂了上面的原理代码就简单了，我们来看下

 1public int[][] findContinuousSequence(int target) {
 2    List<int[]> res = new ArrayList<>();
 3    //因为至少是两个数，所以target先减1
 4    target--;
 5    for (int n = 2; target > 0; n++) {
 6        //找到了一组满足条件的序列
 7        if (target % n == 0) {
 8            int[] arr = new int[n];
 9            //找出首项的值
10            int startValue = target / n;
11            for (int k = 0; k < n; k++) {
12                arr[k] = startValue + k;
13            }
14            res.add(arr);
15        }
16        target -= n;
17    }
18    Collections.reverse(res);
19    //把list转化为数组
20    return res.toArray(new int[res.size()][]);
21}