1. Runtime Distribution

2. Submission Details

3. Description

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ? j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

4. Example

Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

5. Code

int divideConquer(int64_t* sums, int l, int r, int lower, int upper)
{
    if(l >= r)
    {
        return l == r && sums[l] >= lower && sums[r] <= upper ? 1 : 0;
    }

    int m = l + (r - l >> 1);

    int count = divideConquer(sums, l, m, lower, upper) + divideConquer(sums, m + 1, r, lower, upper);

    int64_t* mergedArray = (int64_t*)malloc(sizeof(int64_t) * (r - l + 1));
    memset(mergedArray, 0, sizeof(int64_t)*(r - l + 1));

    int  x = 0, y = m + 1;
    for (int i = l, j = m + 1, k = m + 1; i <= m;)
    {
        while (j <= r && sums[j] - sums[i] < lower) j++;
        while (k <= r && sums[k] - sums[i] <= upper) k++;
        count += k - j;

        while (y <= r && sums[y] < sums[i]) mergedArray[x++] = sums[y++];
        mergedArray[x++] = sums[i++];
    }

    while (y <= r) mergedArray[x++] = sums[y++];

    for(int i = 0; i< x; i++)
    {
        sums[l + i] = mergedArray[i];
    }

    return count;
}

int countRangeSum(int* nums, int numsSize, int lower, int upper) {

    if(nums == NULL || numsSize == 0 || lower > upper)
    {
        return 0;
    }

    int64_t* sums = (int64_t*)malloc(sizeof(int64_t) * (numsSize + 1));
    memset(sums, 0, sizeof(int64_t)*(numsSize + 1));

    for (int i = 0; i< numsSize; i++) {
        sums[i + 1] = sums[i] + nums[i];
    }
    return divideConquer(sums, 1, numsSize, lower, upper);
}

6.Test

#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int divideConquer(int64_t* sums, int l, int r, int lower, int upper)
{
    if(l >= r)
    {
        return l == r && sums[l] >= lower && sums[r] <= upper ? 1 : 0;
    }

    int m = l + (r - l >> 1);

    int count = divideConquer(sums, l, m, lower, upper) + divideConquer(sums, m + 1, r, lower, upper);

    int64_t* mergedArray = (int64_t*)malloc(sizeof(int64_t) * (r - l + 1));
    memset(mergedArray, 0, sizeof(int64_t)*(r - l + 1));

    int  x = 0, y = m + 1;
    for (int i = l, j = m + 1, k = m + 1; i <= m;)
    {
        while (j <= r && sums[j] - sums[i] < lower) j++;
        while (k <= r && sums[k] - sums[i] <= upper) k++;
        count += k - j;

        while (y <= r && sums[y] < sums[i]) mergedArray[x++] = sums[y++];
        mergedArray[x++] = sums[i++];
    }

    while (y <= r) mergedArray[x++] = sums[y++];

    for(int i = 0; i< x; i++)
    {
        sums[l + i] = mergedArray[i];
    }

    return count;
}

int countRangeSum(int* nums, int numsSize, int lower, int upper) {

    if(nums == NULL || numsSize == 0 || lower > upper)
    {
        return 0;
    }

    int64_t* sums = (int64_t*)malloc(sizeof(int64_t) * (numsSize + 1));
    memset(sums, 0, sizeof(int64_t)*(numsSize + 1));

    for (int i = 0; i< numsSize; i++) {
        sums[i + 1] = sums[i] + nums[i];
    }
    return divideConquer(sums, 1, numsSize, lower, upper);
}

int main()
{
    int nums[] = { -2, 5, -1 };
    printf("%d\n", countRangeSum(nums, 3, -2, 2));
    system("pause");
    return 0;
}