博客

// 在数组中查找某个和为连续正数数列的(至少两个)和为给定值
// 思路：
// 注意这里是连续的正数数列，因此如果采用O(n^2)遍历的方式会有大量重复计算
// 可以利用去重复计算减少计算量，两个指针一个指向连续数列开始，一个指向连续数列结尾
// 然后计算和，小于给定值则向后移动尾指针，大于则移动头指针
int find_sum_num(int a[], int n, int k)
{
    if (a == nullptr || n < 2 || k <= 0)
    {
        return -1;
    }

    int start = 0;
    int end = 0;
    int sum = a[0];
    for (start = 0, end = 0; end < n;)
    {
        if (sum < k && end < n)
        {
            end++;
            sum += a[end];
        }
        else if (sum > k)
        {
            sum -= a[start];
            start++;
            if (start > end && end < n)
            {
                end++;
            }
        }
        else
        {
            for (int i = start; i <= end; i++)
            {
                cout << a[i] << " ";
            }
            return 0;
        }
    }

    return -1;
}

// 给定一个正数n，打印全部的连续正数数列(至少两个)和为n的数列，例如15=1+2+3+4+5=4+5+6=7+8
// 思路：
// 这里因为是采用连续正数数列，可以和上述方法一致，两个指针，一个指向连续数列头，一个指向连续数列尾
// 然后遍历从0到n/2的数字，找出全部的连续数列即可
int find_continuous_seq(int n)
{
    if (n < 2)
    {
        return -1;
    }

    int sum = 1;
    for (int start = 1, end = 1; end <= n/2 + 1;)
    {
        if (sum == n)
        {
            for (int i = start; i <= end; i++)
            {
                cout << i << " ";
            }
            cout << endl;
        }
        else if (sum < n)
        {
            end++;
            sum += end;
        }
        else
        {
            sum -= start;
            start++;
        }
    }

    return 0;
}