1543：剑指offer面试题57 -II 和为s的连续正数序列

问题描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例

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

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

限制：
1 <= target <= 10⁵

思路

想了一下，感觉抓住了什么又感觉没抓住。
最近心情不好，脑子也乱。(so,校招时保持状态非常重要，不要让不良因素影响你)
所以只能写出个暴力的，然后再细细的考虑了。
暴力法：认为每个以小于target的数字开头的序列都有机会成为结果，由于每次查找结果，结果都会是一个等差数列，根据等差数列求和公式，我们得知每次查找的时间复杂度是O(√target)。由于我们要遍历target次，所以总的时间复杂度是O(target*√target).(方法一)
经过观察， 外层循环中，以target/2+1开头的元素一定不符合题意。为啥呢？因为(target/2+1)*2>target。所以我们可以把范围缩减到target/2中。这样会有微弱的时间提升，但是总的时间复杂度量级是不变的。（方法一改进版）
这题可以用数学公式做，但是工程类的问题尽量不要用公式，我们只把官方题解放在这里，不给出实现了。

最好的办法是双指针法。我们通过观察暴力法，暴力法有个特点，跟kmp算法比较像，暴力法之所以效率低，是因为第一：我们每次都是对元素进行累加，而不是用等差数列求和公式计算；第二，为什么暴力法不能用等差数列求和公式？因为我们是用累加的，如果对于每个累加都计算一遍，还不如直接累加效率高；第三，为什么我们用双指针法就可以用等差数列求和公式呢？因为我们的right指针不需要回溯。
我们设置left为左边界，right为右边界。left,right的初始值分别为1，2代表了右边界。(题目说了解集中每个数组至少含两个数)。 所以这也指明了我们的退出条件：如果left追上了right，那么以后就不可能有解了。
一共有三种情况：
target == sum: 这种情况是符合的，直接构建解集，加入最终解集。记得加入后，更新left和right。因为这代表这个left和right符合条件了，要继续查找下一个。
target < sum: 这种情况是我们的序列大了，由于我们的左右指针的移动方向都是向右移动，所以我们缩减sum的手段只有一个：右移左指针，这就相当于把当前的待查序列的头掐掉了。 即left++;
target > sum: 这种情况是我们的序列小了，同理，我们应该给待查序列接上一个尾巴，即right++;

(方法二)

方法一

Java版

public int[][] findContinuousSequence1(int target) {
        int[][] res = new int[target][];
        int count = 0;
        for(int i = 1; i < target/2+1; i++){
            int[] cur = new int[target];
            int remains = target;
            int innerCount = 0;
            for(int j = i; j <= remains; j++){
                cur[innerCount++] = j;
                remains -= j;
            }
            if(remains == 0){
                // 可以加入
                int[] curTrue = new int[innerCount];
                for(int k = 0; k < innerCount; k++){
                    curTrue[k] = cur[k];
                }
                res[count++] = curTrue;
            }
        }
        int[][] trueRes = new int[count][];
        for(int i = 0; i < count; i++){
            trueRes[i] = res[i];
        }
        return trueRes;
    }

方法二

Java版

public int[][] findContinuousSequence(int target) {
        int[][] res = new int[target][];
        int count = 0;
        for(int left = 1, right = 2; left < right;){
            int curSum = (left+right)*(right-left+1)/2;
            if(curSum == target){
                // 写入
                int[] tmp = new int[right-left+1];
                int tmpIndex = 0;
                for(int k = left; k <= right; k++){
                    tmp[tmpIndex++] = k;
                }
                res[count++] = tmp;
                left++;
                right++;
            }else if(curSum < target){
                right++;
            }else{
                left++;
            }
        }
        int[][] trueRes = new int[count][];
        for(int i = 0; i < count; i++){
            trueRes[i] = res[i];
        }
        return trueRes;
    }