剑指offer 57-II.和为s的连续正数序列。

       由于找工作笔试和毕业搞大论文有一段时间没更新过博客了。今天感觉刷题效果不错，同时也是总结一些知识点。就对这道剑指offer的题进行一下描述。其中思路是参考大佬的想法，然后写的C语言的代码。如果有那些错误的地方还请指出批评，文末有参考的链接。

本文的解题方法有三种：

一：枚举+暴力

　　

 

/*相应解释看指针处代码
int** findContinuousSequence(int target, int* returnSize, int** returnColumnSizes){
    int limit,i,j,k;
    int x,y;
    if(target%2==0)
    {
        limit=target/2;
    }
    else
    {
        limit=(target+1)/2;
    }
    
    int retsize=0;
    int *retcolsize=(int *)malloc(sizeof(int)*target);
    int **output=(int **)malloc(sizeof(int *)*target);
    int index=0;
    for(i=1;i<=limit;i++)
    {
        int sum=0,count=0;
        for(j=i;;j++)
        {
            sum+=j;
            count++;
            if(sum>=target)        //只有当大于等于跳出后，才能进行sum==target的判断。若只是大于的话，输出不了结果
            {
                break;
            }
        }
        if(sum==target)
        {
            output[index]=(int *)malloc(sizeof(int)*count);
            int ii=0;
            for(k=i;k<=j;k++)
            {
                output[index][ii++]=k;
            }
            retcolsize[index]=count;
            index++;
            retsize++;
        }
    }
    *returnColumnSizes=retcolsize;
    *returnSize=retsize;
    return output;


}

 

二：枚举+数学优化

 

 

int** findContinuousSequence(int target, int* returnSize, int** returnColumnSizes){
    int limit,i,j,k;
    int x,y;
    if(target%2==0)
    {
        limit=target/2;
    }
    else
    {
        limit=(target+1)/2;
    }
    
    int retsize=0;
    int *retcolsize=(int *)malloc(sizeof(int)*target);
    int **output=(int **)malloc(sizeof(int *)*target);
    int index=0;
    
    for(x=1;x<=limit;x++)
    {
        long long delta=1-4*(x-pow(x,2)-2*target);
        if(delta<0) continue;
        int delta_sqrt=sqrt(delta+0.5);
        if(pow(delta_sqrt,2)==delta&&(delta_sqrt-1)%2==0)
        {
            y=(-1+delta_sqrt)/2;
            if(x<y)
            {
                output[index]=(int *)malloc(sizeof(int)*limit);
                int ii=0;
                for(i=x;i<=y;i++)
                {
                    output[index][ii++]=i;
                }
                retcolsize[index]=y-x+1;
                retsize++;
                index++;
            }
        }
    }
    *returnColumnSizes=retcolsize;
    *returnSize=retsize;
    return output;

}

 

三：双指针

 

 

int** findContinuousSequence(int target, int* returnSize, int** returnColumnSizes){
    int i,j=1,limit=target/2+1;    //i和j相当于描述中的l和r,limit则是数学优化中描述的界限.
    int *retcolsize=(int *)malloc(sizeof(int)*target);  //用来记录满足要求的若干数组中分别包含多少个数。
    int **output=(int **)malloc(sizeof(int *)*target); //用来存储满足条件的数组
    int index=0;    //用来记录有输出中有几个满足要求的数组个数
    int sum=0,k=0; //sum是计算相邻数字和的结果，
    for(i=1;i<=limit;i++)
    {
        sum+=i;
        while(sum>target)   //当sum大于target时，此时应该枚举下一个起点，
        {
            sum-=j;
            j++;
        }
        if(sum==target)   //相等时
        {
            int m=0;
            output[index]=(int *)malloc(sizeof(int)*target);
            for(k=j;k<=i;k++)
            {
                output[index][m++]=k;      //存储合法解
            }
            retcolsize[index]=i-j+1;
      
            index++;
        }
    }
//下面这两步是必须的。是记录数组个数，以及数组中的数组包含几个元素
    *returnColumnSizes=retcolsize;              
    *returnSize=index;             
    return output;
}

 

 参考资料链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/mian-shi-ti-57-ii-he-wei-sde-lian-xu-zheng-shu-x-2/