LeetCode 面试题57 - II. 和为s的连续正数序列

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

示例
输入:target = 9
输出:[[2,3,4],[4,5]]

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

看到这个题首先想到了,双指针
由举例可以看出来,最大的数为target /2,也是可以理解的,要求最少含有两个数,则中间两个数相加的话如果满足条件,那么他就是最少数的范围,其他的范围皆在左边

class Solution {
    public int[][] findContinuousSequence(int target) {
        List <int []> res = new ArrayList<>();
        int left=1;
        int right=2;
        int sum=left+right;
        for(;left<right && right<=target/2+1;){
            if(sum==target){
                int [] s=new int[right-left+1];
                for(int i=0;i<=right-left;i++)s[i]=left+i;
                res.add(s);
                sum-=left;
                left++;
                right++;
                sum+=right;
            }else if(sum>target){
                sum-=left;
                left++;
            }else{
            	right++;
                sum+=right;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

写完之后看题解,看到了等差数列的解法,用公式求解,神奇,棒棒哒。
这里也学习一下

序列用数学表示为 (x+y)(xy+1)/2=target(x+y)*(x-y+1)/2=target(x+y)∗(x−y+1)/2=target
那么知道了x的情况下,并且也给了target,也就可以算出y;
这里还是约分一下公式。记录一下。
化成一行 表示 x2xy2y+2t=0x ^2 −x−y ^2 −y+2t=0x2−x−y2−y+2t=0
其中x其实是一个常数
求根公式,x1,2=b±b24ac2ax_1,_2 = \frac{-b±\sqrt{b^2-4ac} }{2a}x1​,2​=2a−b±b2−4ac​​
根据题意可知x永远是正整数,所以直接可以去掉负数根,就得到:
x=y2+y2t+1412x= \sqrt{y^2+y-2t+\frac{1}{4}}-\frac{1}{2}x=y2+y−2t+41​​−21​

代码懒得敲了,下一个也是用到了这个公式。

间隔法。
还是这个公式(x+y)(xy+1)/2=target(x+y)*(x-y+1)/2=target(x+y)∗(x−y+1)/2=target
假设x和y的距离为i 那么i=y-x;
进一步化简
2xi+2x+i2+i=2t2xi+2x+i^2+i=2t2xi+2x+i2+i=2t
t=x(i+1)+i(i+1)/2t=x(i+1)+i(i+1)/2t=x(i+1)+i(i+1)/2
最终x=ti(i1)2i+1x=\frac{t-\frac{i(i-1)}{2}}{i+1}x=i+1t−2i(i−1)​​
根据这个式子
可以得出一些条件
1.x必须是正整数,所以i(i1)2<t\frac{i(i-1)}{2}<t2i(i−1)​<t
2.ti(i1)2i+1\frac{t-\frac{i(i-1)}{2}}{i+1}i+1t−2i(i−1)​​必须是整数
所以可以轻易求出x,之后根据i=y-x求出y
这里一定要注意,i从大到小遍历
代码如下:

class Solution {
    public int[][] findContinuousSequence(int target) {
        List <int []> res = new ArrayList<>();
        int i=target/2+1;
        while(i>0){
            if(i*(i-1)>=2*target){
                i--;
                continue;
            }
            if ((target - i*(i+1)/2)!=0 && (target - i*(i+1)/2) % (i+1)==0){
                int x= (target - i*(i+1)/2)/(i+1);
                int y=i+x;
                int [] s=new int[i+1];
                for(int k=0;k<=i;k++)s[k]=x+k;
                res.add(s);
            }
            i--;
        }
        return res.toArray(new int[res.size()][]);
    }
}

这里送上终极代码。
大家可以看规律,
用i表示符合要求的长度,
那么数组长度就是以target/i为中心向左右扩散,
左右分别i/2,但是如果是i是偶数的情况下,我们占用了一个左边的位置,
那么左边就剩下(i-1)/2 我们惊喜的发现,即使i是是奇数,左边的数值,也满足条件
求出左边界和右边界,如果出界就跳出(我感觉跳出条件可以优化,但是想不出来了)

class Solution {
    public int[][] findContinuousSequence(int target) {
        List <int []> res = new ArrayList<>();
        for(int i=2;i<target/2+1;i++){
            int l=target/i-(i-1)/2;
            int r=target/i+i/2;
            if(l<1 || r> target)break;
            if((l+r)*(r-l+1)/2==target){
                int [] s=new int[r-l+1];
                for(int k=0;k<i;k++)s[k]=k+l;
                res.add(s);
            }
        }
        Collections.reverse(res);
        return res.toArray(new int[res.size()][]);
    }
}
上一篇:JS数据请求与响应


下一篇:面试题57 - II. 和为s的连续正数序列