[好题!] 剑指offer 57 - 2 连续正整数的和

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

滑动窗口解法

/**
 * 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){
    *returnSize = 0;
    if (target <= 2) return NULL;
    int **ret = malloc(sizeof(int*) * sqrt(target));
    *returnColumnSizes = malloc(sizeof(int) * sqrt(target));

    int sum;
    int head = 1, tail = 2;
    while(tail <= target/2 + 1)
    {
        sum = (tail - head + 1) * (head + tail) / 2;
        
        if(sum == target)
        {
            int *temp = malloc(sizeof(int ) * (tail -head + 1));
            ret[*returnSize] = temp;
            (*returnColumnSizes)[*returnSize] = tail -head + 1;
            (*returnSize)++;
            for(int i = head; i<=tail; i++)
            {
                *temp = i;
                temp++;
            }
            head++;
            tail = head + 1;
        }
        else if(sum < target)
        {
            tail++;
        }
        else if(sum > target)
        {
            head++;
            tail = head + 1;
        }
    }
    return ret;
}

时间复杂度: N
空间复杂度: 1