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

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

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);
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include 
#include 
#include 
#include 

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;
}

[/restab]
[/restabs]