11.leetcode 剑指offer（剑指 Offer 57 - II. 和为 s 的连续正数序列）c语言

109 阅读 0 评论 72 点赞

我是靠谱客的博主能干小熊猫，这篇文章主要介绍11.leetcode 剑指offer（剑指 Offer 57 - II. 和为 s 的连续正数序列）c语言，现在分享给大家，希望可以做个参考。

1.题目：

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

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

2.示例：

示例 1：

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

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

3.解题思路：

签：滑动窗口、指针
整体思路：
最容易想到的思路就是暴力枚举，因为题目条件要求至少含有两个数，所以枚举到 target/2 即可停止，时间复杂度较高
更好的方式是使用滑动窗口，设立左右指针，从开始位置维护一个子数组作为窗口，判断该窗口是否求和为 target，如果是则将结果加入，如果小于 target 则窗口右移，大于 target 则窗口左移

4.代码：

复制代码

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** findContinuousSequence(int target, int* returnSize, int** returnColumnSizes){
  int l;
    int r;
    int sum = 0;
    int **rets;//代表指向二维数组的指针
    int *col;//代表指向一维数组的指针，它用来保存每行的元素个数
    int i = 0;
    int n = 0;//代表一行的元素个数
    int m = 0;//代表行号

if(target == 0)
    {
        *returnSize = 0;
        **returnColumnSizes = 0;
        return NULL;
    }

rets = (int **)malloc(sizeof(int *)*target);
    col = (int *)malloc(sizeof(int)*target);

for(l=1, r=2; l < r;)
    {
        sum = ((l+r) * (r-l+1))/2;
        if(sum < target)
        {
            r++;
        }
        else if(sum > target)
        {
            l++;
        }
        else
        {
            rets[m] = (int *)malloc(sizeof(int)*(r - l + 1));
            for(i = l,n=0; i <= r; i++)
            {
                rets[m][n++] = i; 
            }
            col[m] = n;//代表m行有len个元素
            m++;

l++;
        }
    }

*returnSize = m;
    *returnColumnSizes = col;

return rets;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** findContinuousSequence(int target, int* returnSize, int** returnColumnSizes){
  int l;
    int r;
    int sum = 0;
    int **rets;//代表指向二维数组的指针
    int *col;//代表指向一维数组的指针，它用来保存每行的元素个数
    int i = 0;
    int n = 0;//代表一行的元素个数
    int m = 0;//代表行号

    if(target == 0)
    {
        *returnSize = 0;
        **returnColumnSizes = 0;
        return NULL;
    }

    rets = (int **)malloc(sizeof(int *)*target);
    col = (int *)malloc(sizeof(int)*target);

    for(l=1, r=2; l < r;)
    {
        sum = ((l+r) * (r-l+1))/2;
        if(sum < target)
        {
            r++;
        }
        else if(sum > target)
        {
            l++;
        }
        else
        {
            rets[m] = (int *)malloc(sizeof(int)*(r - l + 1));
            for(i = l,n=0; i <= r; i++)
            {
                rets[m][n++] = i; 
            }
            col[m] = n;//代表m行有len个元素
            m++;

            l++;
        }
    }

    *returnSize = m;
    *returnColumnSizes = col;

    return rets;
}